이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 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... |