Submission #411655

#	Time	Username	Problem	Language	Result	Execution time	Memory
411655		A_D	Rice Hub (IOI11_ricehub)	C++14	17 / 100	16 ms	2252 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL NN=1e5+100;
LL a[NN];
LL pre[NN];
LL n,b;
bool ok(LL mid)
{
    LL l=1,r=mid,me=0;
    while(r<=n){
        LL avg=(pre[r]-pre[l-1])/mid;
        while(a[me+1]<=avg&&me<n){
            me++;
        }
        LL ret=avg*(me-l+1)-(pre[me]-pre[l-1]);
        ret+=(pre[r]-pre[me])-avg*(r-me);
        if(ret<=b)return 1;
        avg++;
        while(a[me+1]<=avg&&me<n){
            me++;
        }
        ret=avg*(me-l+1)-(pre[me]-pre[l-1]);
        ret+=(pre[r]-pre[me])-avg*(r-me);
        if(ret<=b)return 1;
        l++;
        r++;
    }
    return 0;
}
int besthub(int R, int L, int X[], long long B)
{
    n=R;
    b=B;
    for(LL i=0;i<R;i++)a[i+1]=X[i];
    for(LL i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
    LL l=1,r=n,ans=0;
    while(l<=r){
//        cout<<5<<endl;
        LL mid=(l+r)/2;
        if(ok(mid)){
            l=mid+1;
            ans=mid;
        }
        else r=mid-1;
    }
    int ann=ans;
    return ann;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32