oj.uz

Submission #543240

# Submission time Handle Problem Language Result Execution time Memory
543240 2022-03-29T23:38:24 Z Deepesson Hacker (BOI15_hac) C++17
0 / 100
 83 ms 33228 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]={};
    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

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 33168 KB Output is correct
2 Correct 72 ms 33152 KB Output is correct
3 Correct 73 ms 33136 KB Output is correct
4 Correct 71 ms 33100 KB Output is correct
5 Correct 69 ms 33080 KB Output is correct
6 Correct 69 ms 33136 KB Output is correct
7 Correct 69 ms 33132 KB Output is correct
8 Correct 83 ms 33212 KB Output is correct
9 Correct 68 ms 33164 KB Output is correct
10 Correct 66 ms 33124 KB Output is correct
11 Correct 69 ms 33096 KB Output is correct
12 Incorrect 74 ms 33228 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 33168 KB Output is correct
2 Correct 72 ms 33152 KB Output is correct
3 Correct 73 ms 33136 KB Output is correct
4 Correct 71 ms 33100 KB Output is correct
5 Correct 69 ms 33080 KB Output is correct
6 Correct 69 ms 33136 KB Output is correct
7 Correct 69 ms 33132 KB Output is correct
8 Correct 83 ms 33212 KB Output is correct
9 Correct 68 ms 33164 KB Output is correct
10 Correct 66 ms 33124 KB Output is correct
11 Correct 69 ms 33096 KB Output is correct
12 Incorrect 74 ms 33228 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 33164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 33168 KB Output is correct
2 Correct 72 ms 33152 KB Output is correct
3 Correct 73 ms 33136 KB Output is correct
4 Correct 71 ms 33100 KB Output is correct
5 Correct 69 ms 33080 KB Output is correct
6 Correct 69 ms 33136 KB Output is correct
7 Correct 69 ms 33132 KB Output is correct
8 Correct 83 ms 33212 KB Output is correct
9 Correct 68 ms 33164 KB Output is correct
10 Correct 66 ms 33124 KB Output is correct
11 Correct 69 ms 33096 KB Output is correct
12 Incorrect 74 ms 33228 KB Output isn't correct
13 Halted 0 ms 0 KB -