Submission #1217416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217416		countless	Rice Hub (IOI11_ricehub)	C++20	100 / 100	12 ms	1220 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

int besthub(int R, int L, int X[], ll B) {
    // possible to take x elements in B cost
    auto check = [&](int x) -> bool {
        if (x == 1) return true;
        if (x == 2) {
            for (int i = 1; i < R; i++) {
                if (X[i] - X[i-1] <= B) return true;
            }

            return false;
        }

        ll best = LLONG_MAX, curr = 0;

        int amt = x;
        amt--;

        deque<int> left, right;
        int m = (amt + 1) / 2;
        int med = X[m];

        int ind = 0;
        for (ind = 0; ind < m; ind++) left.push_back(X[ind]), curr += (med - X[ind]);
        ind++; // take med
        for (; ind < x; ind++) right.push_back(X[ind]), curr += (X[ind] - med);

        best = min(best, curr);

        // ensure ll later
        for (int i = x; i < R; i++) {
            curr -= (med - left.front()); left.pop_front();
            left.push_back(med); med = right.front();
            curr += (med - left.back()) * left.size();
            curr -= (med - left.back()) * right.size();
            right.pop_front(); right.push_back(X[i]);
            curr += (X[i] - med);

            best = min(best, curr);
        }

        return best <= B;
    };

    int l = 0, r = R;
    while (r - l > 1) {
        int m = (l + r) / 2;

        if (check(m)) {
            l = m;
        } else {
            r = m;
        }
    }

    if (check(r)) l = r;

    return l;
}

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