Submission #543244

#	Time	Username	Problem	Language	Result	Execution time	Memory
543244		Deepesson	Hacker (BOI15_hac)	C++17	100 / 100	390 ms	73776 KiB

hac

#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]={};
      |                   ^~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40