제출 #411670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
411670		A_D	쌀 창고 (IOI11_ricehub)	C++14	17 / 100	22 ms	2244 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
#define LL long long
using namespace std;
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=a[me]*(me-l+1)-(pre[me]-pre[l-1]);
        ret+=(pre[r]-pre[me])-a[me]*(r-me);
        if(ret<=b)return 1;
        me++;
        ret=a[me]*(me-l+1)-(pre[me]-pre[l-1]);
        ret+=(pre[r]-pre[me])-a[me]*(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];
    sort(a+1,a+n+1);
    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