Submission #598957

#	Time	Username	Problem	Language	Result	Execution time	Memory
598957		Summers	Rice Hub (IOI11_ricehub)	C++14	100 / 100	13 ms	1500 KiB

ricehub

#include "ricehub.h"
#include<iostream>
using namespace std;
long long pref[1000000];
int besthub(int R, int L, int X[], long long B)
{
    long long i, ans=0, le, ri, mid;

    for(i=0;i<R;i++)
    {
       if(i!=0) pref[i]=pref[i-1]+X[i];
       else pref[i]=X[i];
    }

    le=0; ri=0;

    while(ri<R)
    {
        mid=(le+ri)/2;

        long long ledist= 0, ridist = pref[ri]-pref[mid];

        if(le>=1 && mid>=1)ledist = pref[mid-1]-pref[le-1];
        else if(mid>=1)ledist=pref[mid-1];

        long long sum=((mid-le)*X[mid]-ledist)+(ridist-(ri-mid)*(X[mid]));

        if(sum<=B)
        {
            ans=max(ans, ri-le+1);
            ri++;
        }
        else
        {
            le++;
            ri++;
        }

    }

    return ans;
}

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