제출 #26409

#제출 시각아이디문제언어결과실행 시간메모리
26409zscoderHacker (BOI15_hac)C++14
40 / 100
1000 ms37104 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<ll> vi; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<ll>::iterator sit; typedef map<ll,ll>::iterator mit; int a[1000011]; int pref[1000011]; int S(int l, int r) { if(l==0) return pref[r]; else return pref[r]-pref[l-1]; } int s[1000011]; int n; int ans[1000011]; const int INF = int(2e9)+200; int f1[1000011]; int f2[1000011]; int f3[1000011]; int f4[1000011]; void del(map<int,int> &ma, int v) { ma[v]--; if(ma[v]==0) ma.erase(v); } #define scan(x) do{while((_n=getchar())<45);if(_n-45)x=_n;else x=getchar();for(x-=48;47<(_=getchar());x=(x<<3)+(x<<1)+_-48);if(_n<46)x=-x;}while(0) char _, _n; int main() { scan(n); for(int i=0;i<n;i++) { scan(a[i]); a[n+i]=a[i]; } for(int i=0;i<2*n;i++) { pref[i]=a[i]; if(i>0) pref[i]+=pref[i-1]; } for(int i=0;i<n;i++) { int l = i; int r = i + (n-1)/2; s[i] = S(l,r); s[n+i]=s[i]; } for(int i=0;i<n;i++) { ans[i]=min(s[i],s[i+(n-1)/2]); ans[i+n]=INF; } for(int id=0;id<2*n;id++) { f1[id]=s[(id+1)]; if(id+2<2*n) f2[id]=max(min(s[id],s[(id+2)]),s[(id+1)]); if(id+1<2*n) f3[id]=max(s[id+1],s[id]); if(id+2<2*n) f4[id]=min(max(s[id],s[(id+2)]),s[(id+1)]); } int k = (n+1)/2; if(n&1) { { map<int,int> ma; int L = -k/2+1+(k%2==0); int R = 0; //ans[i] update by min of [i - R, i - L] for(int i = max(-R, 0); i <= min(-L, n); i++) ma[f1[i]]++; for(int i=0;i<n;i++) { if(!ma.empty()) { ans[i]=min(ans[i],(ma.begin())->fi); } if(i+1<n) { if(i+1-L>=0&&i+1-L<2*n) { ma[f1[i+1-L]]++; } if(i-R>=0&&i-R<2*n) { del(ma,f1[i-R]); } } } } { map<int,int> ma; int L = -k/2+1+(k%2==0); int R = 0; //ans[i] update by min of [i - R, i - L] for(int i = max(-R, 0); i <= min(-L, n); i++) ma[f1[i]]++; for(int i=0;i<n;i++) { if(!ma.empty()) { ans[i]=min(ans[i],(ma.begin())->fi); } if(i+1<n) { if(i+1-L>=0&&i+1-L<2*n) { ma[f1[i+1-L]]++; } if(i-R>=0&&i-R<2*n) { del(ma,f1[i-R]); } } } } if(n>2) { { map<int,int> ma; int L = -(k-1)/2+1+(k&1); int R = 0; //ans[i] update by min of [i - R, i - L] for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f2[i]]++; for(int i=0;i<n;i++) { if(!ma.empty()) { ans[i]=min(ans[i],(ma.begin())->fi); } if(i+1<n) { if(i+1-L>=0&&i+1-L<2*n) { ma[f2[i+1-L]]++; } if(i-R>=0&&i-R<2*n) { del(ma,f2[i-R]); } } } } { map<int,int> ma; int L = 3-k; int R = 3-k+(k-1)/2-(k&1)-1; //ans[i] update by min of [i - R, i - L] for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f2[i]]++; for(int i=0;i<n;i++) { if(!ma.empty()) { ans[i]=min(ans[i],(ma.begin())->fi); } if(i+1<n) { if(i+1-L>=0&&i+1-L<2*n) { ma[f2[i+1-L]]++; } if(i-R>=0&&i-R<2*n) { del(ma,f2[i-R]); } } } } } } else { { map<int,int> ma; int L = -k/2+1; int R = 0; //ans[i] update by min of [i - R, i - L] for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f3[i]]++; for(int i=0;i<n;i++) { if(!ma.empty()) { ans[i]=min(ans[i],(ma.begin())->fi); } if(i+1<n) { if(i+1-L>=0&&i+1-L<2*n) { ma[f3[i+1-L]]++; } if(i-R>=0&&i-R<2*n) { del(ma,f3[i-R]); } } } } { map<int,int> ma; int L = 2-k; int R = 2-k+k/2-1; //ans[i] update by min of [i - R, i - L] for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f3[i]]++; for(int i=0;i<n;i++) { if(!ma.empty()) { ans[i]=min(ans[i],(ma.begin())->fi); } if(i+1<n) { if(i+1-L>=0&&i+1-L<2*n) { ma[f3[i+1-L]]++; } if(i-R>=0&&i-R<2*n) { del(ma,f3[i-R]); } } } } if(n>2) { { map<int,int> ma; int L = -(k-1)/2+1; int R = 0; //ans[i] update by min of [i - R, i - L] for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f4[i]]++; for(int i=0;i<n;i++) { if(!ma.empty()) { ans[i]=min(ans[i],(ma.begin())->fi); } if(i+1<n) { if(i+1-L>=0&&i+1-L<2*n) { ma[f4[i+1-L]]++; } if(i-R>=0&&i-R<2*n) { del(ma,f4[i-R]); } } } } { map<int,int> ma; int L = 3-k; int R = 3-k+(k-1)/2-1; //ans[i] update by min of [i - R, i - L] for(int i = max(-R, 0); i <= min(-L, 2*n); i++) ma[f4[i]]++; for(int i=0;i<n;i++) { if(!ma.empty()) { ans[i]=min(ans[i],(ma.begin())->fi); } if(i+1<n) { if(i+1-L>=0&&i+1-L<2*n) { ma[f4[i+1-L]]++; } if(i-R>=0&&i-R<2*n) { del(ma,f4[i-R]); } } } } } } int res=0; for(int i=0;i<n;i++) { res=max(res,min(ans[i],ans[i+n])); } printf("%d\n",res); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...