Submission #598939

#	Time	Username	Problem	Language	Result	Execution time	Memory
598939		daisy2	Rice Hub (IOI11_ricehub)	C++14	100 / 100	16 ms	2516 KiB

ricehub

#include<iostream>
#include "ricehub.h"
using namespace std;
long long pr[100005];
int besthub(int R, int L, int X[], long long B)
{
    pr[0]=X[0];
    for(int i=1;i<R;i++)
      pr[i]=pr[i-1]+X[i];

    long long le,l,r,bud,bx,prl,prr,md=0;
    for(int ri=0;ri<R;ri++)
    {
        l=0;r=ri;
        while(l<=r)
        {
            le=(l+r)/2;

            bx=(ri+le)/2;

            prl=0;
            if(le>0 && bx>0)
               prl=(pr[bx-1]-pr[le-1]);
            else if(bx>0)
                prl=pr[bx-1];

            prr=pr[ri]-pr[bx];

            bud=X[bx]*(bx-le)-prl+prr-X[bx]*(ri-bx);

            if(bud>B)
              l=le+1;
            else r=le-1;
        }
        md=max(md,(ri-l+1));
    }

    return md;
}

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