Submission #49436

#	Time	Username	Problem	Language	Result	Execution time	Memory
49436		ho94949	Rice Hub (IOI11_ricehub)	C++17	100 / 100	22 ms	15732 KiB

ricehub

#include "ricehub.h"

bool can(int g, int N, long long S[], int X[], long long B)
{
    for(int l=1; l<=N-g+1; ++l)
    {
        //[l, r]
        int r = l+g-1; 
        int m = (l+r)/2;
        
        //[l, m-1]
        long long lsum = (long long)(m-l)*X[m] - (S[m-1] - S[l-1]);
        //[m+1, r]
        long long rsum = (S[r] - S[m]) - (long long)(r-m)*X[m];
        if(lsum+rsum <= B) return true;
    }
    return false;
}

int besthub(int R, int L, int X[], long long B)
{
    long long *S = new long long[R+1];
    S[0] = 0;
    for(int i=1; i<=R; ++i)
        S[i] = S[i-1] + X[i-1];
    int lo = 0; //pos
    int hi = R+1; //impos
    while(lo+1!=hi)
    {
        int mi = (lo+hi)/2;
        if(can(mi, R, S, X-1, B)) lo = mi; //tweak, make X 1-indexed
        else hi = mi;
    }
    return lo;
}

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