Submission #543240

#	Time	Username	Problem	Language	Result	Execution time	Memory
543240		Deepesson	Hacker (BOI15_hac)	C++17	0 / 100	83 ms	33228 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];
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]={};
    for(int i=0;i!=N;++i){
        respostas[i]=seg(i,i+puxa-1);
       /// std::cout<<i<<" "<<i+puxa-1<<" "<<respostas[i]<<"\n";
        if(i){
            left[i-1]=std::max(left[i-1],respostas[i]);
        }
        if(i+puxa<N){
            right[i+puxa]=std::max(right[i+puxa],respostas[i]);
        }
    }
    ll total[N]={};
    {
        ll p=0;
        for(int i=0;i!=N;++i){
            p=std::max(p,right[i]);
            total[i]=std::max(total[i],p);
        }
        p=0;
        for(int i=N-1;i!=-1;--i){
            p=std::max(p,left[i]);
            total[i]=std::max(total[i],p);
        }
      /*  for(int i=0;i!=N;++i){
            std::cout<<total[i]<<" ";
        }
        std::cout<<"\n";*/
    }
    std::cout<<(soma-(*std::min_element(total,&total[N])))<<"\n";
}

Compilation message (stderr)

hac.cpp: In function 'int main()':
hac.cpp:46:8: warning: unused variable 'ans' [-Wunused-variable]
   46 |     ll ans=0;
      |        ^~~

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