제출 #720821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
720821		Ahmed57	Hacker (BOI15_hac)	C++14	100 / 100	270 ms	22732 KiB

hac

#include <bits/stdc++.h>

using namespace std;
int n;long long arr[500001];
long long st[500001];
long long pref[500001];
long long seg[2000001];
long long ge(int l,int r){
    if(r>=l){
        return pref[r]-(l==0?0:pref[l-1]);
    }else{
        return (pref[n-1]-(l==0?0:pref[l-1]))+pref[r];
    }
}
void build(int p,int l,int r){
    if(l==r){
        seg[p] = st[l-1];
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[p]= max(seg[p*2],seg[p*2+1]);
}
long long query(int p,int l,int r,int lq,int rq){
    if(l>=lq&&r<=rq)return seg[p];
    if(l>rq||r<lq)return 0;
    int md = (l+r)/2;
    return max(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
long long val(int l,int r){
    if(r>=l){
        return query(1,1,n,l+1,r+1);
    }else{
        return max(query(1,1,n,l+1,n),query(1,1,n,1,r+1));
    }
}
signed main(){
    cin>>n;
    int seg = n/2;
    for(int i = 0;i<n;i++){
        cin>>arr[i];
        pref[i] = arr[i];
        if(i)pref[i]+=pref[i-1];
    }for(int i = 0;i<n;i++){
        st[i] = ge(i,(i+seg-1)%n);
    }
    build(1,1,n);
    long long ans = 0;
    for(int i = 0;i<n;i++){
        long long l = (i+1)%n;
        long long r = ((i-seg)%n+n)%n;
        ans = max(ans,pref[n-1]-val(l,r));
    }
    cout<<ans<<endl;
}

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