oj.uz

Submission #543235

# Submission time Handle Problem Language Result Execution time Memory
543235 2022-03-29T23:22:48 Z Deepesson Hacker (BOI15_hac) C++17
0 / 100
 82 ms 33260 KB 
#include <bits/stdc++.h>
#define MAX 2100000
#define LSB(A) (A&(-A))
using ll = long long;
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 puxa=N/2;
    ll ans=0;
    for(int i=N;i!=2*N;++i){
        ll ans1 = seg(i+1,i+puxa),ans2=seg(i-puxa,i-1);
        ans=std::max(ans,soma-std::max(ans1,ans2));
    }
    std::cout<<ans<<"\n";
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 33260 KB Output is correct
2 Incorrect 74 ms 33144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 33260 KB Output is correct
2 Incorrect 74 ms 33144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 33096 KB Output is correct
2 Incorrect 64 ms 33164 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 33260 KB Output is correct
2 Incorrect 74 ms 33144 KB Output isn't correct
3 Halted 0 ms 0 KB -