记录编号	45423	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十二]圆圈舞蹈	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.055 s
提交时间	2012-10-23 22:03:47	内存使用	1.07 MiB

#include <cstdio>
#include <cstdlib>
#include <deque>
#include <algorithm>
using namespace std;
const int MAXN=200010;
int N,Num[MAXN]={0},half;
deque<int> q;
int main()
{
	freopen("circlea.in","r",stdin);
	freopen("circlea.out","w",stdout); 
	scanf("%d\n",&N);
	for(int i=1;i<=N;i++) scanf("%d\n",&Num[i]),Num[i+N]=Num[i];
	for(int i=1;i<=N+N;i++) Num[i]+=Num[i-1];
	half=Num[N]/2; //printf("%d\n",half);
	q.push_back(0); int ans=0;
	for(int i=1;i<=N*2-1;i++)
	{ 
		while(q.size() && Num[i]-q.front()>half) q.pop_front();
		if(q.size()) {if(ans<Num[i]-q.front()) ans=Num[i]-q.front();}
		q.push_back(Num[i]);
	} printf("%d\n",ans);
	return 0;
}