Submission #26831

#	Time	Username	Problem	Language	Result	Execution time	Memory
26831		yutaka1999	Hacker (BOI15_hac)	C++14	100 / 100	166 ms	33268 KiB

hac

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define SIZE 500005

using namespace std;
typedef long long int ll;

ll sum[SIZE*2];
ll ans[SIZE*2];

int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		ll a;
		scanf("%lld",&a);
		sum[i]=a;
		if(i>0) sum[i]+=sum[i-1];
	}
	for(int i=n;i<2*n;i++) sum[i]=sum[n-1]+sum[i-n];
	for(int i=0;i<n;i++) ans[i]=sum[n-1];
	int L=(n+1)/2;
	priority_queue <ll,vector <ll>,greater <ll> > que,rem;
	for(int i=2*n-1;i>=L;i--)
	{
		if(i>=L-1) que.push(sum[i]-(i==L-1?0:sum[i-L]));
		if(i+L<=2*n-1) rem.push(sum[i+L]-sum[i]);
		while(!rem.empty()&&rem.top()==que.top()) que.pop(),rem.pop();
		ans[i%n]=min(ans[i%n],que.top());
	}
	ll ret=0;
	for(int i=0;i<n;i++) ret=max(ret,ans[i]);
	printf("%lld\n",ret);
	return 0;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:18:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
hac.cpp:22:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a);
                   ^

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40