Submission #873864

#	Time	Username	Problem	Language	Result	Execution time	Memory
873864		1075508020060209tc	Hacker (BOI15_hac)	C++14	100 / 100	114 ms	26196 KiB

hac

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int ar[1000006];
int ps[1000006];
int pok[1000006];

int ok(int mi){
for(int i=1;i<=n+n;i++){
    pok[i]=0;
}
int len=(n+1)/2;
for(int i=len;i<=n+n;i++){
    pok[i]=0;
    if(ps[i]-ps[i-len]>=mi){
        pok[i]=1;
    }
}
for(int i=1;i<=n+n;i++){
    pok[i]+=pok[i-1];
}
for(int i=len;i<=n+n;i++){
    if(pok[i]-pok[i-len]==len){
        return 1;
    }
}
return 0;
}
int br[1000006];

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
        ar[i+n]=ar[i];
    }
    for(int i=1;i<=n+n;i++){
        ps[i]=ar[i]+ps[i-1];
    }
    int len=(n+1)/2;
    for(int i=len;i<=n+n;i++){
        br[i]=ps[i]-ps[i-len];
    }
    deque<int>dq;
    for(int i=len;i<=len+len-1;i++){
        while(dq.size()&&br[dq.front()]>=br[i]){dq.pop_front();}
        dq.push_front(i);
    }
    int ans=br[dq.back()];
    for(int i=len+len;i<=n+n;i++){
        if(dq.back()==i-len){dq.pop_back(); }
        while(dq.size()&&br[dq.front()]>=br[i]){dq.pop_front();}
        dq.push_front(i);
        ans=max(ans,br[dq.back()]);
        
    }
    cout<<ans<<endl;
}

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