제출 #26409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
26409		zscoder	Hacker (BOI15_hac)	C++14	40 / 100	1000 ms	37104 KiB

hac

#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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 40