oj.uz

Submission #723578

# Submission time Handle Problem Language Result Execution time Memory
723578 2023-04-14T05:41:48 Z Erkinoff_Mohammed Hacker (BOI15_hac) C++14
0 / 100
 1 ms 212 KB 
#include "bits/stdc++.h"
using namespace std;
#define INF 2000000000
#define INFLL 3000000000000000000LL
#define ll long long

struct segtree{
    
    
    vector<ll>tree;
    int size=1;
    
    void init(int n){
        while(size<n)size<<=1;
        tree.assign(size*2-1, 0);
    }
    
    void update(int i, ll val, int x, int lx, int rx){
        if(rx-lx==1)tree[x]=val;
        else{
            int mid=(lx+rx)/2;
            if(i<mid)update(i,val, x*2+1,lx,mid);
            else update(i,val, x*2+2,mid,rx);
            tree[x]=max(tree[x*2+1],tree[x*2+2]);
        }
    }
    
    void update(int i, ll val){
        update(i,val, 0,0,size);
        //for(int i=size-1;i<size*2-1;i++)cout<<tree[i]<<' ';
        //cout<<"\n";
    }
    
    ll get(int ql, int qr, int x, int lx, int rx){
        if(ql>=rx||lx>=qr)return 0;
        if(ql<=lx&&rx<=qr)return tree[x];
        else{
            int mid=(lx+rx)/2;
            return max(get(ql,qr, x*2+1,lx,mid),get(ql,qr, x*2+2,mid,rx));
        }
    }
    
    ll get(int ql,int qr){
        if(ql>=qr)return 0;
        return get(ql,qr,0,0,size);
    }
    
};



int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    ll arr[n];
    ll sum=0;
    ll sum2=0;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        sum+=arr[i];
        if(i<n/2)sum2+=arr[i];
    }
    segtree seg;
    seg.init(n);
    for(int i=0;i<n;i++){
        seg.update(i,sum2);
        sum2-=arr[i];
        sum2+=arr[(i+n/2)%n];
    }
    ll mx=0;
    for(int i=0;i<n;i++){
        ll sum2=max(seg.get(0,i-(n+1)/2+1),seg.get(i+1,n));
        //cout<<sum2<<"\n";
        ll mn=sum-sum2;
        mx=max(mx,mn);
    }
    cout<<mx;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Halted 0 ms 0 KB -