Submission #1224997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224997		akqxolotl	Hacker (BOI15_hac)	C++20	100 / 100	327 ms	22080 KiB

hac

//Segment Tree is a State of Mind
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugl(x) cerr << #x << " is "; for(auto p : x) cerr << p << " "; cerr << endl;
#define debugpl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p.first<<" "<<p.second<<endl;cerr<<endl;

#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()

int inf=4e18+5;
int mod=1e9+7;

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
	int n;cin>>n;
	int a[2*n];
	int t=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		t+=a[i];
		a[i+n]=a[i];
	}
	deque<int> dq;
	multiset<int> s;
	int w=n/2;
	int cs=0,ans=0;
	for(int i=1;i<1+w;i++){
		cs+=a[i];
	}
	dq.pb(cs);
	s.insert(cs);
	int l=1;
	for(int r=1+w;r<n;r++){
		cs+=a[r];
		cs-=a[l];
		dq.pb(cs);
		s.insert(cs);
		l++;
	}
	//debugl(dq)
	ans=t-(*(--s.end()));
	//debug(ans)
	for(int r=n;r<2*n;r++){
		int old=dq.front();
		s.erase(s.find(old));
		dq.pop_front();
		cs+=a[r];
		cs-=a[l];
		l++;
		dq.pb(cs);
		s.insert(cs);
		//debugl(dq)
		ans=max(ans,t-(*(--s.end())));
		//debug(ans)
	}
	
	cout<<ans<<'\n';
		
}

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