oj.uz

Submission #543241

# Submission time Handle Problem Language Result Execution time Memory
543241 2022-03-29T23:43:57 Z Deepesson Hacker (BOI15_hac) C++17
0 / 100
 78 ms 33156 KB 
#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

hac.cpp: In function 'int main()':
hac.cpp:51:19: warning: unused variable 'r' [-Wunused-variable]
   51 |         int l = i,r=(i+puxa-1)%N;
      |                   ^
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.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 33124 KB Output is correct
2 Incorrect 78 ms 33080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 33124 KB Output is correct
2 Incorrect 78 ms 33080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 33156 KB Output is correct
2 Incorrect 70 ms 33088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 33124 KB Output is correct
2 Incorrect 78 ms 33080 KB Output isn't correct
3 Halted 0 ms 0 KB -