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;
deque<int> q;
void ins(int x){
while (!q.empty() && q.back() > x){
q.pop_back();
}
q.push_back(x);
}
void ers(int x){
if (!q.empty() && q.front() == x){
q.pop_front();
}
}
int getmn(){
return q.front();
}
int main() {
int n;
cin >> n;
vector<int> a(2*n);
for (int i = 0; i<n; i++){
cin >> a[i];
a[n+i] = a[i];
}
vector<int> res;
int k = (n+1)/2;
int sm = 0;
for (int i = 0; i<k; i++){
sm += a[i];
}
res.push_back(sm);
for (int i = k; i<n+k-1; i++){
sm -= a[i-k];
sm += a[i];
res.push_back(sm);
}
for (int i = 0; i<n; i++){
res.push_back(res[i]);
}
vector<int> ans(n, 1e9);
for (int i = 0; i<k; i++){
ins(res[i]);
}
ans[k-1] = getmn();
for (int i = k; i<2*n; i++){
ers(res[i-k]);
ins(res[i]);
int ind = i; if (ind >= n) ind -= n;
ans[ind] = getmn();
}
int mx = 0;
for (auto u : ans){
mx = max(mx,u);
}
cout << mx << '\n';
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... |