제출 #1119851

#제출 시각아이디문제언어결과실행 시간메모리
1119851PagodePaivaHacker (BOI15_hac)C++17
100 / 100
169 ms43188 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...