Submission #730708

#	Time	Username	Problem	Language	Result	Execution time	Memory
730708		lucri	Rice Hub (IOI11_ricehub)	C++17	100 / 100	15 ms	2480 KiB

ricehub

#include "ricehub.h"
#include <stdio.h>
#include <stdlib.h>
long long sum[100010];
int besthub(int R, int L, int X[], long long B)
{
    for(int i=0;i<R;++i)
        sum[i+1]=sum[i]+X[i];
    int b=0,e=R;
    while(b<=e)
    {
        int mid=(b+e)/2;
        bool ok=false;
        for(int i=0;i+mid-1<R;++i)
        {
            long long suma=1LL*X[(i+i+mid-1)/2]*((i+i+mid-1)/2-i)-(sum[(i+i+mid-1)/2]-sum[i]);
            suma+=(sum[i+mid]-sum[(i+i+mid-1)/2+1])-1LL*X[(i+i+mid-1)/2]*(i+mid-1-(i+i+mid-1)/2);
            if(B>=suma)
                ok=true;
        }
        if(ok==true)
            b=mid+1;
        else
            e=mid-1;
    }
    return e;
}

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