#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define fi first #define se second #define all(x) x.begin(),x.end() #define file "file" #define rf if(fopen(file".inp", "r")) {freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);} const int N=5e5+7; int n,a[N]; ll pre[N],mm[25][N],res; int sub(int x, int y) { x-=y; if(x<=0) x+=n; if(x>n) x-=n; return x; } int len(int x, int y) { x-=y; if(x<0) x+=n; return x; } int ad(int x, int y) { x+=y; if(x<=0) x+=n; if(x>n) x-=n; return x; } ll get(int l, int r) { if(l>r) return 0; int len=31-__builtin_clz(r-l+1); // cout<<' '<<l<<' '<<r<<' '<<len<<' '<<mm[len][l]<<' '<<mm[len][r-(1<<len)+1]<<endl; return max(mm[len][l],mm[len][r-(1<<len)+1]); } void prep() { for(int i=1; i<25; i++) for(int j=1; j<=n; j++) { if(j+(1<<i)-1>n) break; mm[i][j]=max(mm[i-1][j],mm[i-1][j+(1<<(i-1))]); // cout<<' '<<i<<' '<<j<<' '<<mm[i][j]<<' '<<mm[i-1][j]<<' '<<mm[i-1][j+(1<<(i-1))-1]<<endl; } } void init() { cin>>n; for(int i=1; i<=n; i++) cin>>a[i]; } void proc() { for(int i=1; i<=n; i++) pre[i]=pre[i-1]+a[i]; for(int i=1; i<=n; i++) { int j=sub(ad(i,n/2),1); ll w; if(j<i) w=pre[j]+pre[n]-pre[i-1]; else w=pre[j]-pre[i-1]; mm[0][i]=w; // cout<<i<<' '<<j<<' '<<w<<endl; } prep(); // cout<<get(1,3)<<' '<<get(3,5); // cout<<pre[n]<<endl; for(int i=1; i<=n; i++) { int j=sub(i,n/2); ll w; if(j>i) w=get(i+1,j); else w=max(get(i+1,n),get(1,j)); // cout<<i<<' '<<i-n/2<<' '<<sub(i,n/2)<<' '<<get(1,i-n/2)<<' '<<w<<endl; res=max(res,pre[n]-w); } cout<<res; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); rf; init(); proc(); }

hac.cpp: In function 'int main()':
hac.cpp:10:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define rf if(fopen(file".inp", "r")) {freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:98:5: note: in expansion of macro 'rf'
   98 |     rf;
      |     ^~
hac.cpp:10:80: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | #define rf if(fopen(file".inp", "r")) {freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);}
      |                                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
hac.cpp:98:5: note: in expansion of macro 'rf'
   98 |     rf;
      |     ^~