제출 #1235434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235434		erering	Hacker (BOI15_hac)	C++20	100 / 100	192 ms	27880 KiB

hac

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl '\n'
#define int long long
const int N=1e6+5,inf=2e18,MOD=1e9+7;
int seg[N*4],pref[N],offset=1,a[N];
void update(int idx,int val){
    idx+=offset;
    seg[idx]=val;
    idx/=2;
    while(idx>0){
        seg[idx]=max(seg[idx*2],seg[idx*2+1]);
        idx/=2;
    }
}
int query(int node,int qlo,int qhi,int lo,int hi){
    if(lo>=qlo && hi<=qhi)return seg[node];
    if(lo>qhi || hi<qlo)return -inf;
    int mid=(lo+hi)/2;
    return max(query(node*2,qlo,qhi,lo,mid),query(node*2+1,qlo,qhi,mid+1,hi));
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,sum=0,ans=0; cin>>n;
    while(offset<N)offset*=2;
    for(int i=0;i<n*2;i++){
        if(i<n){
            cin>>a[i];
            sum+=a[i];
        }
        else{
            a[i]=a[i%n];
         //   cout<<a[i]<<' '<<i-(n%2?n/2+1:n/2)<<' '<<i-1<<endl;
            ans=max(ans,sum-query(1,i-(n%2?n/2+1:n/2),i-1,0,offset-1));
        }
        pref[i]=a[i];
        if(i>0)pref[i]+=pref[i-1];
        if(i>=n/2-1)update(i,pref[i]-(i-n/2>=0?pref[i-n/2]:0));
    }
    cout<<ans;
}

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