Submission #106881

#	Time	Username	Problem	Language	Result	Execution time	Memory
106881		Pajaraja	Hacker (BOI15_hac)	C++17	100 / 100	106 ms	12664 KiB

hac

#include <bits/stdc++.h>
#define MAXN 500007
using namespace std; 
int a[MAXN],sm[MAXN],pr[MAXN],n,p,lg[MAXN],ng[MAXN];
int sum(int r)
{
	if(r>=p) return pr[r]-pr[r-p];
	else return pr[r]+(pr[n]-pr[n-p+r]);
}
int dist(int l,int r)
{
	if(r>l) return r-l;
	else return n-l+r;
}
int main()
{
	scanf("%d",&n); p=(n+1)/2;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) pr[i]=pr[i-1]+a[i];
	for(int i=1;i<=n;i++) sm[i]=sum(i);
	stack<int> st; sm[0]=0; st.push(0);
	for(int i=1;i<=n;i++)
	{
		while(sm[st.top()]>=sm[i]) st.pop();
		st.push(i);
	}
	for(int i=1;i<=n;i++)
	{
		while(sm[st.top()]>=sm[i]) st.pop();
		lg[i]=st.top();
		st.push(i);
	}
	while(!st.empty()) st.pop();
	sm[n+1]=0; st.push(n+1);
	for(int i=n;i>0;i--)
	{
		while(sm[st.top()]>=sm[i]) st.pop();
		st.push(i);
	}
	for(int i=n;i>0;i--)
	{
		while(sm[st.top()]>=sm[i]) st.pop();
		ng[i]=st.top();
		st.push(i);
	}
	int res=0;
	for(int i=1;i<=n;i++) if(dist(lg[i],i)+dist(i,ng[i])>=p+1) res=max(res,sm[i]);
	printf("%d",res);
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n); p=(n+1)/2;
  ~~~~~^~~~~~~~~
hac.cpp:18:29: 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("%d",&a[i]);
                        ~~~~~^~~~~~~~~~~~

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