Submission #60838

#	Time	Username	Problem	Language	Result	Execution time	Memory
60838		Vahan	Rice Hub (IOI11_ricehub)	C++17	17 / 100	41 ms	7100 KiB

ricehub

#include "ricehub.h"
#include<algorithm>
using namespace std;
int x[200000];
long long su[200000];
int bin(int l,int r,int v)
{
    if(l==r)
        return l;
    if(l==r-1)
    {
        if(x[r]<=v)
            return r;
        else
            return l;
    }
    int mid=(l+r)/2;
    if(x[mid]<=v)
        return bin(mid,r,v);
    else
        return bin(l,mid-1,v);
}
long long pat(int l,int r)
{
    long long mig=(su[r]-su[l]+x[l])/(r-l+1);
    long long f,e;
    if((su[r]-su[l]+x[l])%(r-l+1)==0)
    {
        e=bin(l,r,mig);
        return (e-l+1)*mig+su[l]-x[l]+su[r]-(r-e)*mig-2*su[e];
    }
    else
    {
        e=bin(l,r,mig);
        f=bin(l,r,mig+1);
        return min((e-l+1)*mig+su[l]-x[l]+su[r]-(r-e)*mig-2*su[e],(f-l+1)*(mig+1)+su[l]-x[l]+su[r]-(r-f)*(mig+1)-2*su[f]);
    }

}
int besthub(int R, int L, int X[], long long B)
{
    for(int r=0;r<R;r++)
    {
        x[r]=X[r];
        if(r==0)
            su[r]=X[r];
        else
            su[r]=su[r-1]+X[r];
    }
    int l=0;
    int an=-1;
    long long q;
    for(int r=0;r<R;r++)
    {
        q=pat(l,r);
        while(q>B)
        {
            l++;
            q=pat(l,r);
        }
        an=max(an,r-l+1);
    }
    return an;
}

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