比赛 20121023 评测结果 EEAAAAAAAA
题目名称 圆圈舞蹈 最终得分 80
用户昵称 苏轼 运行时间 0.212 s
代码语言 C++ 内存使用 1.84 MiB
提交时间 2012-10-23 21:53:39
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<deque>
using namespace std;
int n,ww[200005]={0},w[200005]={0},tmp,sum=0,answer=0;
deque<int>q;
int main()
{
	freopen ("circlea.in","r",stdin);
	freopen ("circlea.out","w",stdout);
	scanf("%d",&n);
	for (int i=2;i<=n+1;i++)
	{
		scanf("%d",&tmp);
		ww[i]=tmp;
		ww[i+n]=tmp;
		w[i]=w[i-1]+tmp;
		sum+=tmp;
	}
	for (int i=n+2;i<=2*n+1;i++)
	{
		w[i]=w[i-1]+ww[i];
	}
	sum/=2;
	q.push_back(w[2]);
	for (int i=3;i<=2*n+1;i++)
	{
		while (w[i]-w[q.front()]>sum&&q.size())
		{
			q.pop_front();
		}
		if (w[i]-w[q.front()]<=sum&&w[i]-w[q.front()]>answer)
			answer=w[i]-w[q.front()];
		q.push_back(i);
	}
	cout<<answer;
	return 0;
}