이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500010;
const int LOGN = 20;
int pref[2*N];
int n;
int v[2*N];
int val[2*N];
struct Segtree{
int tree[8*N];
int join(int a, int b){
return max(a, b);
}
void build(int node, int l, int r){
if(l == r){
tree[node] = val[l];
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
int query(int node, int l, int r, int tl, int tr){
if(l > tr or tl > r) return 0;
if(l <= tl and tr <= r) return tree[node];
int mid =(tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
} seg;
int query(int l, int r){
if(l > r) r += n;
return pref[r]-pref[l-1];
}
int32_t main(){
int n;
cin >> n;
for(int i = 1;i <= n;i++){
cin >> v[i];
v[n+i] = v[i];
}
for(int i = 1;i <= 2*n;i++){
pref[i] = pref[i-1]+v[i];
}
//int res = 0;
int d = n/2;
int sum = 0;
for(int i = 1;i <= d;i++){
sum += v[i];
}
for(int i = 1;i+d-1 <= 2*n;i++){
val[i] = sum;
if(i+d > 2*n) break;
sum -= v[i];
sum += v[i+d];
}
seg.build(1, 1, 2*n);
int res = 0;
for(int i = 1;i <= n;i++){
int l = i, r = i+n;
int tot = pref[r]-pref[l]-seg.query(1, l+1,r-d, 1, 2*n);
res = max(res, tot);
}
cout << res << '\n';
}
# | 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... |