Submission #127040

#	Time	Username	Problem	Language	Result	Execution time	Memory
127040		TadijaSebez	Hacker (BOI15_hac)	C++11	100 / 100	98 ms	22520 KiB

hac

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1000050;
int a[N];
ll sum[N],p[N];
int main()
{
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]),a[i+n]=a[i];
	for(int i=1;i<=n*2;i++) sum[i]=sum[i-1]+a[i];
	int sz=n+1>>1;
	for(int i=1;i<=n;i++) p[i]=sum[i+sz-1]-sum[i-1];
	for(int i=n+1;i<=n*2;i++) p[i]=p[i-n];
	deque<int> dq;
	for(int i=n-sz+2;i<=n;i++)
	{
		while(dq.size() && p[dq.back()]>=p[i]) dq.pop_back();
		dq.push_back(i);
	}
	ll ans=0;
	for(int i=n+1;i<=2*n;i++)
	{
		while(dq.size() && p[dq.back()]>=p[i]) dq.pop_back();
		dq.push_back(i);
		while(dq.front()<i-sz+1) dq.pop_front();
		ans=max(ans,p[dq.front()]);
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:13:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int sz=n+1>>1;
         ~^~
hac.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
hac.cpp:11:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&a[i]),a[i+n]=a[i];
                        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

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