제출 #949255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
949255		Muhammad_Aneeq	Hacker (BOI15_hac)	C++17	100 / 100	211 ms	11356 KiB

hac

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/

#include <iostream>
using namespace std;
int const N=5e5+10;
int St[4*N]={};
int pre[N]={};
int n;
void update(int i,int r,int st,int en,int val)
{
    if (st==en)
    {
        St[i]=val;
        return;
    }
    int mid=(st+en)/2;
    if (r<=mid)
        update(i*2,r,st,mid,val);
    else
        update(i*2+1,r,mid+1,en,val);
    St[i]=max(St[i*2],St[i*2+1]);
}
int get(int i,int st,int en,int l,int r)
{
    if (st>r||en<l)
        return 0;
    if (st>=l&&en<=r)
        return St[i];
    int mid=(st+en)/2;
    return (max(get(i*2,st,mid,l,r),get(i*2+1,mid+1,en,l,r)));
}
inline void solve()
{
    cin>>n;
    int a[n];
    for (auto& i:a)
        cin>>i;
    for (int i=0;i<n;i++)
        pre[i+1]=pre[i]+a[i];
    int ans=0;
    for (int i=0;i<n;i++)
    {
        if (i+n/2>n)
        {
            int z=pre[n]-pre[i];
            int f=i+n/2-n;
            z+=pre[f];
            update(1,i,0,n-1,z);
        }
        else
        {
            int z=pre[i+n/2]-pre[i];
            update(1,i,0,n-1,z);
        }
    }
    for (int i=0;i<n;i++)
    {
        int f=i-n/2;
        f=(f+n)%n;
        int g=i+1;
        if (g<f)
            ans=max(ans,pre[n]-get(1,0,n-1,g,f));
        else
        {
            int z=max(get(1,0,n-1,g,n-1),get(1,0,n-1,0,f));
            ans=max(ans,pre[n]-z);
        }
    }
    cout<<ans<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
        solve();
}

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