This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define append push_back
#define add insert
#define nl "\n"
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define N 500001
int n;
int a[N];
int Add[N];
int REM[N];
map<int,int> Remov;
int get(int l,int r){
if(l>r)
return a[n]-a[l-1]+a[r];
return a[r]-a[l-1];
}
void solve(){
int m,o;
cin>>n;
m=n/2;
for(int i=o=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1];
}
for(int i=1;i<m;i++){
Add[i+1]=get(n-m+i+1,i);
REM[n-m+i+1]=get(n-m+i+1,i);
}
Add[m+1]=get(1,m);
priority_queue<int> Q;
for(int i=m+1;i<=n;i++){
Q.push(get(i-m+1,i));
Add[i+1]=get(i-m+1,i);
REM[i-m+1]=get(i-m+1,i);
}
for(int i=1;i<=n;i++){
Q.push(Add[i]);
Remov[REM[i]]++;
while(Remov[Q.top()]){
Remov[Q.top()]--;
Q.pop();
}
o=max(o,a[n]-Q.top());
}
cout<<o;
}
int main(){
L0TA;
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |