제출 #953077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953077		PM1	Hacker (BOI15_hac)	C++17	100 / 100	169 ms	12884 KiB

hac

#include <bits/stdc++.h>
using namespace std;
const int mxn=5e5+5;
int n,a[mxn],b[mxn],ans=1e9,num=0;
struct segment{
	int val[(1<<22)];
	void build(int id,int L,int R){
		if(L+1==R){
			val[id]=b[L];
			return;
		}
		int mid=(L+R)/2;
		build(id*2,L,mid);
		build(id*2+1,mid,R);
		val[id]=max(val[id*2],val[id*2+1]);
	}
	int get(int id,int L,int R,int l,int r){
		if(l==L && R==r)
			return val[id];
		int mid=(L+R)/2,res=0;
		if(l<mid)
			res=max(res,get(id*2,L,mid,l,min(r,mid)) );
		if(r>mid)
			res=max(res,get(id*2+1,mid,R,max(l,mid),r) );
		return res;
	}
}seg;
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		num+=a[i];
	}
	int sum=0;
	for(int i=0;i<n/2;i++)
		sum+=a[i];
	for(int i=0;i<n;i++){
		b[i]=sum;
		sum-=a[i];
		sum+=a[(i+n/2)%n];
		//cout<<b[i]<<" ";
	}
	seg.build(1,0,n);
	for(int i=0;i<n;i++){
		int l=(i+1)%n,r=(i-n/2+n)%n,res=0;
		//cout<<l<<" "<<r<<endl;
		if(l<=r)
			res=seg.get(1,0,n,l,r+1);
		else
			res=max(seg.get(1,0,n,l,n),seg.get(1,0,n,0,r+1));
		ans=min(ans,res);
	}
	cout<<num-ans<<endl;
}

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