Submission #1216911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216911		mariamp1	Rice Hub (IOI11_ricehub)	C++20	100 / 100	15 ms	2120 KiB

ricehub

#include "ricehub.h"
#include <vector>
#include <algorithm>
using namespace std;

int besthub(int R, int L, int X[], long long B) {
    vector<long long> a(R + 1), p(R + 1);
    for (int i = 1; i <= R; ++i) a[i] = X[i - 1];
    for (int i = 1; i <= R; ++i) p[i] = p[i - 1] + a[i];

    long long res = 0;
    for (int i = 1; i <= R; ++i) {
        int l = 0, r = R;
        while (l <= r) {
            int m = (l + r) / 2;
            int x = m / 2;
            int y = m - x;

            if (i > (R + 1) / 2) swap(x, y);
            if (i - x - 1 < 0 || i + y > R) {
                r = m - 1;
                continue;
            }

            long long cost = x * a[i] - (p[i - 1] - p[i - x - 1]) + (p[i + y] - p[i]) - y * a[i];
            if (cost <= B) {
                res = max(res, (long long)(x + y + 1));
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
    }
    return res;
}

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