Submission #696124

#	Time	Username	Problem	Language	Result	Execution time	Memory
696124		amirhoseinfar1385	Hacker (BOI15_hac)	C++17	100 / 100	189 ms	7116 KiB

hac

#include<bits/stdc++.h>
using namespace std;
int kaf=(1<<19);
struct segment{
	int seg[(1<<20)];
	segment(){
		for(int i=0;i<(1<<20);i++){
			seg[i]=0;
		}
	}
	void upd(int i,int l,int r,int tl,int tr,int w){
		if(l>r||l>tr||r<tl){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i]=max(seg[i],w);
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		return ;
	}
	int pors(int i){
		if(i==0){
			return 0;
		}
		int d=seg[i];
		d=max(d,pors((i>>1)));
		return d;
	}
};
segment seg;
	int n;


void add(int l,int r,int w){
	if(r>l){
		seg.upd(1,0,kaf-1,0,l-1,w);
		seg.upd(1,0,kaf-1,r+1,n,w);
	}
	else{
		seg.upd(1,0,kaf-1,r+1,l-1,w);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	vector<int>all(n);
	int alls=0;
	for(int i=0;i<n;i++){
		cin>>all[i];
		alls+=all[i];
	}
	int len=n/2;
	int l=0,r=len-1;
	int suma=0;
	for(int j=0;j<len;j++){
		suma+=all[j];
	}
	add(l,r,suma);
	bool f=0;
	while(l!=0||f==0){
		f=1;
		suma-=all[l];
		l++;
		l%=n;
		r++;
		r%=n;
		suma+=all[r];
		add(l,r,suma);
	}
	int mina=1e9+5;
	for(int i=0;i<n;i++){
		mina=min(mina,seg.pors(kaf+i));
	//	cout<<i<<" "<<mina<<"\n";
	}
	int res=alls-mina;
	cout<<res<<"\n";
}

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