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;
const int N = 15e5 + 5;
int n, m, sum, a[N], b[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i + n] = a[i + 2 * n] = a[i];
}
m = (n + 1) / 2;
sum = 0;
for(int i = 1; i <= 3 * n; i++){
sum += a[i];
if(i > m){
sum -= a[i - m];
}
b[i] = sum;
}
deque < int > q;
int ans = 0;
for(int i = 1; i <= 3 * n; i++){
while(!q.empty() && b[q.back()] >= b[i]){
q.pop_back();
}
q.push_back(i);
if(q.front() + m <= i){
q.pop_front();
}
ans = max(ans, b[q.front()]);
}
cout << ans;
}
# | 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... |