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>
#define MAX 2100000
#define LSB(A) (A&(-A))
using ll = long long;
typedef std::pair<ll,ll> pll;
typedef std::pair<ll,pll> plp;
ll ft[MAX];
void update(int t,int k){t+=8;
while(t<MAX){
ft[t]+=k;
t+=LSB(t);
}
}
ll query(int t){t+=8;
ll ans=0;
while(t>0){
ans+=ft[t];
t-=LSB(t);
}
return ans;
}
ll seg(int l,int r){
return query(r)-query(l-1);
}
ll array[MAX];
ll tab[MAX*4];
void update(int l,int r,ll k,int la=0,int ra=MAX-1,int pos=1){
if(ra<l||la>r)return;
if(l<=la&&ra<=r){
tab[pos]=std::max(tab[pos],k);
return;
}
int m = (la+ra)/2;
update(l,r,k,la,m,pos*2);
update(l,r,k,m+1,ra,(pos*2)+1);
}
ll querys(int t,int la=0,int ra=MAX-1,int pos=1){
if(ra<t||la>t)return 0;
if(la==ra){
return tab[pos];
}
int m = (la+ra)/2;
return std::max(tab[pos],std::max(querys(t,la,m,pos*2),querys(t,m+1,ra,(pos*2)+1)));
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int N;
std::cin>>N;
long long soma=0;
for(int i=0;i!=N;++i){
std::cin>>array[i];
soma+=array[i];
}
for(int i=0;i!=MAX;++i){
array[i]=array[i%N];
}
for(int i=0;i!=MAX;++i){
update(i,array[i]);
}
ll respostas[N]={};
ll puxa=N/2;
ll ans=0;
ll left[N]={},right[N]={};
std::vector<plp> vec;
for(int i=0;i!=N;++i){
respostas[i]=seg(i,i+puxa-1);
int l = i,r=(i+puxa-1);
/// std::cout<<l<<" "<<r<<" "<<respostas[i]<<"\n";
vec.push_back({respostas[i],{l,i+puxa-1}});
if(r<N){///Ok
if(r!=N-1){
update(r+1,N-1,respostas[i]);
/// std::cout<<r+1<<" "<<N-1<<" "<<respostas[i]<<"\n";
}
if(l){
/// std::cout<<0<<" "<<l-1<<" "<<respostas[i]<<"\n";
update(0,l-1,respostas[i]);
}
}else {
++r;--l;
r%=N;
if(r<l)std::swap(r,l);
///std::cout<<l<<" "<<r<<" "<<respostas[i]<<"!\n";
update(l,r,respostas[i]);
}
}
ll total[N]={};
{
for(int i=0;i!=N;++i){
total[i]=querys(i);
/// std::cout<<total[i]<<"\n";
}
}
std::cout<<(soma-(*std::min_element(total,&total[N])))<<"\n";
}
Compilation message (stderr)
hac.cpp: In function 'int main()':
hac.cpp:65:8: warning: unused variable 'ans' [-Wunused-variable]
65 | ll ans=0;
| ^~~
hac.cpp:66:8: warning: unused variable 'left' [-Wunused-variable]
66 | ll left[N]={},right[N]={};
| ^~~~
hac.cpp:66:19: warning: unused variable 'right' [-Wunused-variable]
66 | ll left[N]={},right[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... |