Submission #787700

#	Time	Username	Problem	Language	Result	Execution time	Memory
787700		Blagoj	Rice Hub (IOI11_ricehub)	C++17	100 / 100	16 ms	3156 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"

using namespace std;

#define ll long long

int besthub(int R, int L, int x[], ll B) {
    vector<ll> X(R + 1);
    X[0] = -(ll)1e18;
    for (int i = 1; i <= R; i++) X[i] = x[i - 1];
    int l = 1, r = R;
    ll pf[R + 1];
    pf[0] = 0;
    for (int i = 1; i <= R; i++) pf[i] = pf[i - 1] + X[i];
    auto check = [&](int mid) {
        for (int l = 1; l + mid <= R + 1; l++) {
            int r = l + mid - 1;
            int median = (r + l) / 2;
            for (int it = max(l, median - 5); it <= min(r, median + 5); it++) {
                ll sum = 0;
                if (it != l) sum += (it - l) * X[it] - (pf[it - 1] - pf[l - 1]);
                if (it != r) sum += -(r - it) * X[it] + (pf[r] - pf[it]);
                if (sum <= B) return true;
            }
        }
        return false;
    };
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }
    return l - 1;
}

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