# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1171432 | LmaoLmao | Hacker (BOI15_hac) | C++20 | 0 ms | 0 KiB |
x#include<bits/stdc++.h>
#define fi first
#define se second
#define endl '\n'
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using aa = array<ll,5>;
const int N = 1e6;
const int INF = 1e9;
int S[2000005],lz[2000005];
int pre[500005];
void push(int id) {
S[id*2]=min(S[id*2],lz[id]);
S[id*2+1]=min(S[id*2+1],lz[id]);
lz[id*2]=min(lz[id*2],lz[id]);
lz[id*2+1]=min(lz[id*2+1],lz[id]);
lz[id]=1e9;
}
void update(int id,int l,int r,int u,int v,int val) {
if(v < l || r < u) return;
if(u<=l && r<=v) {
//cout << l << ' ' << r << ' ' << id << endl;
S[id]=min(S[id],val);
lz[id]=min(lz[id],val);
return;
}
push(id);
int m=(l+r)/2;
update(id*2,l,m,u,v,val);
update(id*2+1,m+1,r,u,v,val);
S[id]=min(S[id*2],S[id*2+1]);
}
int get(int id,int l,int r,int pos) {
if(pos < l || r < pos) return 0;
if(l==r) {
return S[id];
}
push(id);
int m=(l+r)/2;
int t=get(id*2,l,m,pos);
int t1=get(id*2+1,m+1,r,pos);
return max(t,t1);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen("CHONSO.inp", "r", stdin);
//freopen("CHONSO.out", "w", stdout);
int n;
cin >> n;
for(int i=1;i<=n*4;i++) {
S[i]=1e9;
lz[i]=1e9;
}
for(int i=1;i<=n;i++) {
cin >> pre[i];
pre[i]+=pre[i-1];
}
int k=(n+1)/2;
for(int i=1;i<=n;i++) {
ll sum,sum1;
if(i<k) {
sum=pre[i];
sum+=pre[n]-pre[n-k+i];
update(1,1,n,1,i,sum);
update(1,1,n,n-k+i+1,n,sum);
//cout << n << ' '<< endl;
}
else {
sum=pre[i]-pre[i-k];
update(1,1,n,i-k+1,i,sum);
}
//cout << get(1,1,n,2) << ' ';
}
int ans=0;
for(int i=1;i<=n;i++) {
//cout << get(1,1,n,i) << endl;
ans=max(ans,get(1,1,n,i));
}
cout << ans;
return 0;
}