oj.uz

Submission #696123

# Submission time Handle Problem Language Result Execution time Memory
696123 2023-02-05T15:05:49 Z amirhoseinfar1385 Hacker (BOI15_hac) C++17
0 / 100
 2 ms 4424 KB 
#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,l,r,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));
	}
	int res=alls-mina;
	cout<<res<<"\n";
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4424 KB Output is correct
2 Incorrect 2 ms 4420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4424 KB Output is correct
2 Incorrect 2 ms 4420 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Incorrect 2 ms 4424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4424 KB Output is correct
2 Incorrect 2 ms 4420 KB Output isn't correct
3 Halted 0 ms 0 KB -