# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
926364 | Nonoze | Hacker (BOI15_hac) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2);
void solve() {
int n; cin >> n;
vector<int> a;
int mid=n/2+n%2, x;
int sm=0;
for (int i=0; i<mid; i++) {
cin >> x;
sm+=x;
a.push_back(x);
}
for (int i=mid; i<n; i++) {
cin >> x;
a.push_back(x);
}
vector<int> sum(1, sm);
deque<int> curr;
curr.push_back(0);
for (int i=1; i<mid; i++) {
sum.push_back(sum.back()+a[(i+mid-1)%n]-a[i-1]);
while (!curr.empty() && sum[curr.front()]>=sum[i]) curr.pop_front();
curr.push_front(i);
}
for (int i=mid; i<n; i++) sum.push_back(sum.back()+a[(i+mid-1)%n]-a[i-1]);
int ans=0;
for (int i=mid; i<n+mid; i++) {
ans=max(ans, sum[curr.back()]);
while (!curr.empty() && sum[curr.front()]>=sum[i%n]) curr.pop_front();
if (!curr.empty() && curr.back()==i-mid) curr.pop_back();
curr.push_front(i%n);
}
cout << ans << endl;
return;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}