Submission #873851

#	Time	Username	Problem	Language	Result	Execution time	Memory
873851		1075508020060209tc	Hacker (BOI15_hac)	C++14	100 / 100	185 ms	26276 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;
}


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 l=0;int r=1e9+10;
    while(l<r){
        int mi=l+(r-l+1)/2;
        if(ok(mi)){
            l=mi;
        }else{
            r=mi-1;
        }
    }
    cout<<l;

}

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