Submission #748457

#	Time	Username	Problem	Language	Result	Execution time	Memory
748457		mariowong	Hacker (BOI15_hac)	C++14	100 / 100	94 ms	14736 KiB

hac

#include <bits/stdc++.h>
 
using namespace std;
int n,a[500005],pre[500005],sum,r,l,ans,ttl;
priority_queue <pair<int,int>  > mx;
bool chk(int x,int y,int a1){
	if (x > y){
		if (a1 >= x || a1 <= y)
		return false;
		return true;
	}
	else
	{
		if (x <= a1 && a1 <= y)
		return false;
		return true;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n; ans=2e9;
	for (int i=0;i<n;i++){
		cin >> a[i];
		ttl+=a[i];
	}
	r=n/2-1;
	for (int i=0;i<n/2;i++){
		sum+=a[i];
	}
	for (int i=0;i<n;i++){
		pre[i]=sum;
		sum-=a[i];
		r++; r%=n;
		sum+=a[r];
	}
	l=n/2; r=n-1;
	for (int i=l;i<=r;i++){
		mx.push(make_pair(pre[i],i));
	}
	for (int i=0;i<n;i++){
		while (!mx.empty() && chk(l,r,mx.top().second)){
			mx.pop();
		}
		ans=min(ans,mx.top().first);
		l++; r++; l%=n; r%=n;
		mx.push(make_pair(pre[r],r));
	}
	cout << ttl-ans << "\n";
	return 0;
}

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