Submission #1216898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216898		mariamp1	Rice Hub (IOI11_ricehub)	C++20	0 / 100	0 ms	320 KiB

ricehub

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_R = 1000005;
long long P[MAX_R];

bool can(int k, int n, const vector<int>& X, long long bgt) {
    if (k == 0) return true;
    if (k > n) return false;

    for (int i = 0; i <= n - k; ++i) {
        int lidx = i;
        int ridx = i + k - 1;
        int midx = lidx + k / 2;
        long long cost = 0;
        long long nleft = midx - lidx;
        long long sleft = P[midx] - P[lidx];
        cost += nleft * X[midx] - sleft;

        long long nright = ridx - midx;
        long long sright = P[ridx + 1] - P[midx + 1];
        cost += sright - nright * X[midx];
        if (cost <= bgt) {
            return true;
        }
    }
    return false;
}

int besthub(int n, int min_k, int x_coords[], long long bgt) {
    vector<int> X(x_coords, x_coords + n);
    sort(X.begin(), X.end());
    P[0] = 0;
    for (int i = 0; i < n; ++i) {
        P[i+1] = P[i] + X[i];
    }

    int lo = min_k;
    int hi = n;
    int res = 0;
    while (lo <= hi) {
        int md = lo + (hi - lo) / 2;

        if (can(md, n, X, bgt)) {
            res = md;
            lo = md + 1;
        } else {
            hi = md - 1;
        }
    }

    return res;
}

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