Submission #1238335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238335		liangjeremy	Hacker (BOI15_hac)	C++20	100 / 100	38 ms	9120 KiB

hac

/* liangjeremy - happy! */
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using db=double;
using ll=long long;
using s1l=__int128;// super long long
using lb=long double;// lb is s1ow
// numbers for hashing: b(19260817),mod(998244353)
// another number for hashing:b(137) only
// freopen("deleg.in", "r", stdin);
// freopen("deleg.out", "w", stdout);

int main(){
  	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(0)); 
  	int n; cin>>n; vector<int>a(n+1); int tot=0; vector<int>pre(2*n+1);
  	for(int i=1; i<=n; i++){ cin>>a[i]; tot+=a[i]; a.push_back(a[i]); }
  	for(int i=1; i<=2*n; i++){ pre[i]=pre[i-1]+a[i]; }
  	deque<int>dq; int mx=1e9; int len=(int)n/2; 
  	for(int i=1+len; i<=n; i++){
  		int cur=pre[i]-pre[i-len]; 
  		while(dq.size() && cur>=pre[dq.back()]-pre[dq.back()-len])dq.pop_back();
  		dq.push_back(i);
  	}
  	for(int i=n+1; i<=2*n; i++){
  		int idx=dq.front(); int amt=pre[idx]-pre[idx-len]; mx=min(mx,amt); int cur=pre[i]-pre[i-len];
  		if(dq.front()==i-n+len)dq.pop_front();
  		while(dq.size() && cur>=pre[dq.back()]-pre[dq.back()-len])dq.pop_back();
  		dq.push_back(i);
  	}
  	int idx=dq.front(); int amt=pre[idx]-pre[idx-len]; mx=min(mx,amt); cout<<tot-mx<<'\n';
}

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