Submission #543242

#	Time	Username	Problem	Language	Result	Execution time	Memory
543242		Deepesson	Hacker (BOI15_hac)	C++17	0 / 100	75 ms	33096 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]={};
    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)%N;
        std::cout<<l<<" "<<r<<" "<<respostas[i]<<"\n";
        vec.push_back({respostas[i],{l,i+puxa-1}});
    }
    ll total[N]={};
    {
        for(int i=0;i!=N;++i){
            for(auto&x:vec){
                if(i>=x.second.first&&i<=x.second.second)continue;
                if(x.second.second>=N){
                    int t = x.second.second%N;
                    if(t>=i)continue;
                }
                total[i]=std::max(total[i],x.first);
            }
        }
    }
    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;
      |        ^~~
hac.cpp:47:8: warning: unused variable 'left' [-Wunused-variable]
   47 |     ll left[N]={},right[N]={};
      |        ^~~~
hac.cpp:47:19: warning: unused variable 'right' [-Wunused-variable]
   47 |     ll left[N]={},right[N]={};
      |                   ^~~~~

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