Submission #723589

#	Time	Username	Problem	Language	Result	Execution time	Memory
723589		Erkinoff_Mohammed	Hacker (BOI15_hac)	C++14	100 / 100	201 ms	12428 KiB

hac

#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/2+1),seg.get(i+1,i+(n+1)/2+1));
        //cout<<sum2<<"\n";
        ll mn=sum-sum2;
        mx=max(mx,mn);
    }
    cout<<mx;
}

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