Submission #698836

#	Time	Username	Problem	Language	Result	Execution time	Memory
698836		finn__	Rice Hub (IOI11_ricehub)	C11	100 / 100	18 ms	1724 KiB

ricehub

#include "ricehub.h"

#define max(x, y) ((x) > (y) ? (x) : (y))

int besthub(int R, int L, int X[], long long B)
{
    int *mid = X, *begin = X, *end = X + 1, left = 1, right = 0, max_rice = 0;
    long long cost = 0;

    while (mid < X + R)
    {
        // If the cost on the right are too high to restore balance, move the
        // left pointer first.
        if (end < X + R && cost + *end - *mid > B)
            cost -= *mid - *begin, left--, begin++;
        while (end < X + R && right <= left && cost + *end - *mid <= B)
            cost += *end - *mid, right++, end++;
        max_rice = max(max_rice, left + right);

        if (mid < X + R)
            cost += (left - right) * (*(mid + 1) - *mid);
        mid++, left++, right--;
    }

    return max_rice;
}

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