Submission #31675

#	Time	Username	Problem	Language	Result	Execution time	Memory
31675		Dat160601	Hacker (BOI15_hac)	C++14	100 / 100	183 ms	10884 KiB

hac

#include <bits/stdc++.h>
using namespace std;
int n,a[1000007],pre[1000007],ans=0;
deque <int> cur;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[n+i]=a[i];
    }
    int sz=(n/2)+(n%2);
    for(int i=1;i<=sz;i++){
        pre[1]+=a[i];
    }
    for(int i=2;i<=n;i++){
        pre[i]=pre[i-1]+a[i+sz-1]-a[i-1];
    }
    for(int i=1;i<=n;i++) pre[n+i]=pre[i];
    for(int i=1;i<=2*n;i++){
        while(!cur.empty() && pre[cur.back()]>=pre[i]) cur.pop_back();
        cur.push_back(i);
        if(i-cur.front()==sz) cur.pop_front();
        if(i>=sz) ans=max(ans,pre[cur.front()]);
    }
    cout<<ans;
}

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