Submission #543244

#TimeUsernameProblemLanguageResultExecution timeMemory
543244DeepessonHacker (BOI15_hac)C++17
100 / 100
390 ms73776 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...