답안 #26409 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26409	2017-06-30T04:27:36 Z	zscoder	Hacker (BOI15_hac)	C++14	40 / 100	1000 ms	37104 KB

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

int a[1000011];
int pref[1000011];

int S(int l, int r)
{
	if(l==0) return pref[r];
	else return pref[r]-pref[l-1];
}

int s[1000011];
int n; 
int ans[1000011];
const int INF = int(2e9)+200;
int f1[1000011];
int f2[1000011];
int f3[1000011];
int f4[1000011];

void del(map<int,int> &ma, int v)
{
	ma[v]--;
	if(ma[v]==0) ma.erase(v);
}

#define scan(x) do{while((_n=getchar())<45);if(_n-45)x=_n;else x=getchar();for(x-=48;47<(_=getchar());x=(x<<3)+(x<<1)+_-48);if(_n<46)x=-x;}while(0)
char _, _n;
int main()
{
	scan(n);
	for(int i=0;i<n;i++) 
	{
		scan(a[i]);
		a[n+i]=a[i];
	}
	for(int i=0;i<2*n;i++)
	{
		pref[i]=a[i];
		if(i>0) pref[i]+=pref[i-1];
	}
	for(int i=0;i<n;i++)
	{
		int l = i; int r = i + (n-1)/2;
		s[i] = S(l,r);
		s[n+i]=s[i];
	}
	for(int i=0;i<n;i++)
	{
		ans[i]=min(s[i],s[i+(n-1)/2]);
		ans[i+n]=INF;
	}
	for(int id=0;id<2*n;id++)
	{
		f1[id]=s[(id+1)];
		if(id+2<2*n) f2[id]=max(min(s[id],s[(id+2)]),s[(id+1)]);
		if(id+1<2*n) f3[id]=max(s[id+1],s[id]);
		if(id+2<2*n) f4[id]=min(max(s[id],s[(id+2)]),s[(id+1)]);
	}
	int k = (n+1)/2;
	if(n&1)
	{
		{
			map<int,int> ma;
			int L = -k/2+1+(k%2==0);
			int R = 0;
			//ans[i] update by min of [i - R, i - L]
			for(int i = max(-R, 0); i <= min(-L, n); i++) ma[f1[i]]++;
			for(int i=0;i<n;i++)
			{
				if(!ma.empty())
				{
					ans[i]=min(ans[i],(ma.begin())->fi);
				}
				if(i+1<n)
				{
					if(i+1-L>=0&&i+1-L<2*n)
					{
						ma[f1[i+1-L]]++;
					}
					if(i-R>=0&&i-R<2*n)
					{
						del(ma,f1[i-R]);
					}
				}				
			}
		}
		{
			map<int,int> ma;
			int L = -k/2+1+(k%2==0);
			int R = 0;
			//ans[i] update by min of [i - R, i - L]
			for(int i = max(-R, 0); i <= min(-L, n); i++) ma[f1[i]]++;
			for(int i=0;i<n;i++)
			{
				if(!ma.empty())
				{
					ans[i]=min(ans[i],(ma.begin())->fi);
				}
				if(i+1<n)
				{
					if(i+1-L>=0&&i+1-L<2*n)
					{
						ma[f1[i+1-L]]++;
					}
					if(i-R>=0&&i-R<2*n)
					{
						del(ma,f1[i-R]);
					}
				}				
			}
		}
		if(n>2)
		{
			{
				map<int,int> ma;
				int L = -(k-1)/2+1+(k&1);
				int R = 0;
				//ans[i] update by min of [i - R, i - L]
				for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f2[i]]++;
				for(int i=0;i<n;i++)
				{
					if(!ma.empty())
					{
						ans[i]=min(ans[i],(ma.begin())->fi);
					}
					if(i+1<n)
					{
						if(i+1-L>=0&&i+1-L<2*n)
						{
							ma[f2[i+1-L]]++;
						}
						if(i-R>=0&&i-R<2*n)
						{
							del(ma,f2[i-R]);
						}
					}				
				}
			}
			{
				map<int,int> ma;
				int L = 3-k;
				int R = 3-k+(k-1)/2-(k&1)-1;
				//ans[i] update by min of [i - R, i - L]
				for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f2[i]]++;
				for(int i=0;i<n;i++)
				{
					if(!ma.empty())
					{
						ans[i]=min(ans[i],(ma.begin())->fi);
					}
					if(i+1<n)
					{
						if(i+1-L>=0&&i+1-L<2*n)
						{
							ma[f2[i+1-L]]++;
						}
						if(i-R>=0&&i-R<2*n)
						{
							del(ma,f2[i-R]);
						}
					}				
				}
			}
		}
	}
	else
	{
		{
			map<int,int> ma;
			int L = -k/2+1;
			int R = 0;
			//ans[i] update by min of [i - R, i - L]
			for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f3[i]]++;
			for(int i=0;i<n;i++)
			{
				if(!ma.empty())
				{
					ans[i]=min(ans[i],(ma.begin())->fi);
				}
				if(i+1<n)
				{
					if(i+1-L>=0&&i+1-L<2*n)
					{
						ma[f3[i+1-L]]++;
					}
					if(i-R>=0&&i-R<2*n)
					{
						del(ma,f3[i-R]);
					}
				}				
			}
		}
		{
			map<int,int> ma;
			int L = 2-k;
			int R = 2-k+k/2-1;
			//ans[i] update by min of [i - R, i - L]
			for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f3[i]]++;
			for(int i=0;i<n;i++)
			{
				if(!ma.empty())
				{
					ans[i]=min(ans[i],(ma.begin())->fi);
				}
				if(i+1<n)
				{
					if(i+1-L>=0&&i+1-L<2*n)
					{
						ma[f3[i+1-L]]++;
					}
					if(i-R>=0&&i-R<2*n)
					{
						del(ma,f3[i-R]);
					}
				}				
			}
		}
		if(n>2)
		{
			{
				map<int,int> ma;
				int L = -(k-1)/2+1;
				int R = 0;
				//ans[i] update by min of [i - R, i - L]
				for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f4[i]]++;
				for(int i=0;i<n;i++)
				{
					if(!ma.empty())
					{
						ans[i]=min(ans[i],(ma.begin())->fi);
					}
					if(i+1<n)
					{
						if(i+1-L>=0&&i+1-L<2*n)
						{
							ma[f4[i+1-L]]++;
						}
						if(i-R>=0&&i-R<2*n)
						{
							del(ma,f4[i-R]);
						}
					}				
				}
			}
			{
				map<int,int> ma;
				int L = 3-k;
				int R = 3-k+(k-1)/2-1;
				//ans[i] update by min of [i - R, i - L]
				for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f4[i]]++;
				for(int i=0;i<n;i++)
				{
					if(!ma.empty())
					{
						ans[i]=min(ans[i],(ma.begin())->fi);
					}
					if(i+1<n)
					{
						if(i+1-L>=0&&i+1-L<2*n)
						{
							ma[f4[i+1-L]]++;
						}
						if(i-R>=0&&i-R<2*n)
						{
							del(ma,f4[i-R]);
						}
					}
				}
			}
		}
	}
	int res=0;
	for(int i=0;i<n;i++)
	{
		res=max(res,min(ans[i],ans[i+n]));
	}
	printf("%d\n",res);
}

Subtask #1
20.0 / 20.0

#	결과	메모리	Grader output
1	Correct	33276 KB	Output is correct
2	Correct	33276 KB	Output is correct
3	Correct	33276 KB	Output is correct
4	Correct	33276 KB	Output is correct
5	Correct	33276 KB	Output is correct
6	Correct	33276 KB	Output is correct
7	Correct	33276 KB	Output is correct
8	Correct	33276 KB	Output is correct
9	Correct	33276 KB	Output is correct
10	Correct	33276 KB	Output is correct
11	Correct	33276 KB	Output is correct
12	Correct	33276 KB	Output is correct
13	Correct	33276 KB	Output is correct
14	Correct	33276 KB	Output is correct
15	Correct	33276 KB	Output is correct
16	Correct	33276 KB	Output is correct
17	Correct	33276 KB	Output is correct
18	Correct	33276 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	33276 KB	Output is correct
2	Correct	0 ms	33276 KB	Output is correct
3	Correct	0 ms	33276 KB	Output is correct
4	Correct	0 ms	33276 KB	Output is correct
5	Correct	0 ms	33276 KB	Output is correct
6	Correct	0 ms	33276 KB	Output is correct
7	Correct	0 ms	33276 KB	Output is correct
8	Correct	0 ms	33276 KB	Output is correct
9	Correct	0 ms	33276 KB	Output is correct
10	Correct	0 ms	33276 KB	Output is correct
11	Correct	0 ms	33276 KB	Output is correct
12	Correct	0 ms	33276 KB	Output is correct
13	Correct	0 ms	33276 KB	Output is correct
14	Correct	0 ms	33276 KB	Output is correct
15	Correct	0 ms	33276 KB	Output is correct
16	Correct	0 ms	33276 KB	Output is correct
17	Correct	0 ms	33276 KB	Output is correct
18	Correct	0 ms	33276 KB	Output is correct
19	Correct	0 ms	33276 KB	Output is correct
20	Correct	0 ms	33276 KB	Output is correct
21	Correct	0 ms	33276 KB	Output is correct
22	Correct	3 ms	33276 KB	Output is correct
23	Correct	6 ms	33276 KB	Output is correct
24	Correct	3 ms	33276 KB	Output is correct
25	Correct	9 ms	33276 KB	Output is correct
26	Correct	9 ms	33276 KB	Output is correct
27	Correct	0 ms	33276 KB	Output is correct
28	Correct	0 ms	33276 KB	Output is correct
29	Correct	0 ms	33276 KB	Output is correct
30	Correct	6 ms	33408 KB	Output is correct
31	Correct	6 ms	33408 KB	Output is correct

Subtask #3
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	33276 KB	Output is correct
2	Correct	0 ms	33276 KB	Output is correct
3	Correct	9 ms	33276 KB	Output is correct
4	Correct	189 ms	33936 KB	Output is correct
5	Correct	469 ms	34728 KB	Output is correct
6	Correct	706 ms	35388 KB	Output is correct
7	Correct	889 ms	35652 KB	Output is correct
8	Execution timed out	1000 ms	37104 KB	Execution timed out

Subtask #4
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	33276 KB	Output is correct
2	Correct	0 ms	33276 KB	Output is correct
3	Correct	0 ms	33276 KB	Output is correct
4	Correct	0 ms	33276 KB	Output is correct
5	Correct	0 ms	33276 KB	Output is correct
6	Correct	0 ms	33276 KB	Output is correct
7	Correct	0 ms	33276 KB	Output is correct
8	Correct	0 ms	33276 KB	Output is correct
9	Correct	0 ms	33276 KB	Output is correct
10	Correct	0 ms	33276 KB	Output is correct
11	Correct	0 ms	33276 KB	Output is correct
12	Correct	0 ms	33276 KB	Output is correct
13	Correct	0 ms	33276 KB	Output is correct
14	Correct	0 ms	33276 KB	Output is correct
15	Correct	0 ms	33276 KB	Output is correct
16	Correct	0 ms	33276 KB	Output is correct
17	Correct	0 ms	33276 KB	Output is correct
18	Correct	0 ms	33276 KB	Output is correct
19	Correct	0 ms	33276 KB	Output is correct
20	Correct	0 ms	33276 KB	Output is correct
21	Correct	0 ms	33276 KB	Output is correct
22	Correct	3 ms	33276 KB	Output is correct
23	Correct	6 ms	33276 KB	Output is correct
24	Correct	3 ms	33276 KB	Output is correct
25	Correct	9 ms	33276 KB	Output is correct
26	Correct	9 ms	33276 KB	Output is correct
27	Correct	0 ms	33276 KB	Output is correct
28	Correct	0 ms	33276 KB	Output is correct
29	Correct	0 ms	33276 KB	Output is correct
30	Correct	6 ms	33408 KB	Output is correct
31	Correct	6 ms	33408 KB	Output is correct
32	Correct	0 ms	33276 KB	Output is correct
33	Correct	0 ms	33276 KB	Output is correct
34	Correct	9 ms	33276 KB	Output is correct
35	Correct	189 ms	33936 KB	Output is correct
36	Correct	469 ms	34728 KB	Output is correct
37	Correct	706 ms	35388 KB	Output is correct
38	Correct	889 ms	35652 KB	Output is correct
39	Execution timed out	1000 ms	37104 KB	Execution timed out

답안 #26409

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 20.0

Subtask #4 0 / 40.0

Subtask #1
20.0 / 20.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 20.0

Subtask #4
0 / 40.0