Submission #374255

#	Time	Username	Problem	Language	Result	Execution time	Memory
374255		ijxjdjd	Rice Hub (IOI11_ricehub)	C++14	100 / 100	20 ms	1772 KiB

ricehub

#include "ricehub.h"

using ll = long long;
int besthub(int R, int L, int X[], ll B)
{
    int low = 1;
    int high = R;
    while (low < high) {
        int mid = (low + high+1)/2;
        int l = 0;
        int r = 0;
        int m = (mid-1)/2;
        bool good = false;
        ll bot = 0;
        ll top = 0;
        while (r < mid) {
            if (r < m) {
                bot += X[r];
            }
            else if (r > m) {
                top += X[r];
            }
            r++;
        }
        r--;
        if ((m-l)*X[m]-bot + top-(r-m)*X[m] <= B) {
            good = true;
        }
        while (r+1< R) {
            bot -= X[l];
            top += X[r+1];
            bot += X[m];
            top -= X[m+1];
            r++;
            l++;
            m++;
            if ((m-l)*X[m]-bot + top-(r-m)*X[m] <= B) {
                good = true;
            }
        }
        if (good) {
            low = mid;
        }
        else {
            high = mid-1;
        }
    }
    return low;
}

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