Submission #1139293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139293		Warinchai	Rice Hub (IOI11_ricehub)	C++20	100 / 100	9 ms	3144 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std;
long long pre[100005];
long long suf[100005];
int n;
long long ar[100005];
long long mxx=0;
long long cost(int m){
    long long ans=LLONG_MAX;
    for(int i=1;i+m-1<=n;i++){
        long long l=i,r=i+m-1;
        long long md=(l+r)/2;
        long long cst=pre[r]-pre[md-1]-ar[md]*(r-md+1) + suf[l]-suf[md+1]-(mxx-ar[md])*(md-l+1);
        ans=min(ans,cst);
    }
    return ans;
}
int besthub(int R, int L, int X[], long long B)
{
    mxx=L;
    for(int i=0;i<=R;i++)suf[i]=pre[i]=ar[i]=0;
    n=R;
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+X[i-1];
        //cerr<<pre[i]<<" ";
    }
    //cerr<<"\n";
    for(int i=n;i>=1;i--){
        suf[i]=suf[i+1]+L-X[i-1];
        //cerr<<suf[i]<<" ";
    }
    //cerr<<"\n";
    for(int i=1;i<=n;i++)ar[i]=X[i-1];
    int st=1,en=R,ans=0;
    while(st<=en){
        int m=(st+en)/2;
        long long x=cost(m);
        //cerr<<m<<" "<<x<<"\n";
        if(x<=B){
            st=m+1;
            ans=m;
        }else{
            en=m-1;
        }
    }
    return ans;
}

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