AtCoder B - Pizza

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 200200 points

Problem Statement

We have a circular pizza.
Takahashi will cut this pizza using a sequence AA of length NN, according to the following procedure.

• First, make a cut from the center in the 1212 o'clock direction.
• Next, do NN operations. The ii-th operation is as follows.
  • Rotate the pizza A_iAi​ degrees clockwise.
  • Then, make a cut from the center in the 1212 o'clock direction.

For example, if A=(90,180,45,195)A=(90,180,45,195), the procedure cuts the pizza as follows.

Find the center angle of the largest pizza after the procedure.

Constraints

• All values in input are integers.
• 1 \le N \le 3591≤N≤359
• 1 \le A_i \le 3591≤Ai​≤359
• There will be no multiple cuts at the same position.

---

Input

Input is given from Standard Input in the following format:

NN
A_1A1​ A_2A2​ \dots… A_NAN​

Output

Print the answer as an integer.

---

Sample Input 1 Copy

Copy

4
90 180 45 195

Sample Output 1 Copy

Copy

120

This input coincides with the example in the Problem Statement.
The center angle of the largest pizza is 120120 degrees.

---

Sample Input 2 Copy

Copy

1
1

Sample Output 2 Copy

Copy

359

---

Sample Input 3 Copy

Copy

10
215 137 320 339 341 41 44 18 241 149

Sample Output 3 Copy

Copy

170

 

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
inline int read()
{
	int x = 0, y = 1;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-')  y = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
		x = x * 10 + c - '0', c = getchar();
	return x * y;
}
 
typedef unsigned long long LL;

typedef pair<LL, LL> PII;
 
const int N = 1e6 + 10;

int n, q, res, m, cnt, maxm;
bool f[N];


signed main()
{
	n = read();
	f[0] = true;
	for(int i = 1; i <= n; i ++ )
	{
		int x;
		x = read();
		res += x; res %= 360;
		f[res] = true;
	}
	for(int i = 0; i <= 360; i ++ )
	{
		if(f[i % 360])  
		{
			maxm = max(maxm, cnt);
			cnt = 0;
		}
		cnt ++;
	}
	cout << maxm << endl;
}