Submission #1216892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216892		lukasuliashvili	Rice Hub (IOI11_ricehub)	C++20	100 / 100	9 ms	1864 KiB

ricehub

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

bool can(int k, int R, long long B, const vector<int>& X, const vector<long long>& prefix) {
    for (int i = 0; i + k - 1 < R; i++) {
        int j = i + k - 1;
        int mid = (i + j) / 2;

        long long leftSum = (mid > 0 ? prefix[mid - 1] : 0LL) - (i > 0 ? prefix[i - 1] : 0LL);
        long long rightSum = prefix[j] - prefix[mid];

        int leftCount = mid - i;
        int rightCount = j - mid;

        long long leftCost = 1LL * X[mid] * leftCount - leftSum;
        long long rightCost = rightSum - 1LL * X[mid] * rightCount;
        long long totalCost = leftCost + rightCost;

        if (totalCost <= B)
            return true;
    }
    return false;
}

int besthub(int R, int L, int X_raw[], long long B) {
    vector<int> X(X_raw, X_raw + R);
    sort(X.begin(), X.end());

    vector<long long> prefix(R);
    prefix[0] = X[0];
    for (int i = 1; i < R; i++) {
        prefix[i] = prefix[i - 1] + X[i];
    }

    int low = 1, high = R, best = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (can(mid, R, B, X, prefix)) {
            best = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return best;
}

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