Submission #1115556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115556		vjudge1	Rice Hub (IOI11_ricehub)	C++17	Compilation error	0 ms	0 KiB

ricehub

#include <iostream>
#include <vector>
#include <numeric>
#include <climits>

using namespace std;
using ll = long long;

bool isFeasible(int m, int R, vector<ll>& X, ll B, vector<ll>& prefix_sum) {
    if (m == 0) return true;
    int median_pos = (m - 1) / 2;
    ll min_sum = LLONG_MAX;
    for (int l = 0; l <= R - m; ++l) {
        int r = l + m - 1;
        int med = l + median_pos;
        ll sum_left = X[med] * (med - l) - (prefix_sum[med - 1] - (l > 0 ? prefix_sum[l - 1] : 0));
        ll sum_right = (prefix_sum[r] - prefix_sum[med]) - X[med] * (r - med);
        ll total_sum = sum_left + sum_right;
        if (total_sum < min_sum) {
            min_sum = total_sum;
            if (min_sum <= B) break;
        }
    }
    return min_sum <= B;
}

int besthub(int R, int L, vector<int>& X, ll B) {
    vector<ll> X_ll(R);
    for (int i = 0; i < R; ++i) X_ll[i] = X[i];
    vector<ll> prefix_sum(R + 1, 0);
    for (int i = 1; i <= R; ++i) prefix_sum[i] = prefix_sum[i - 1] + X_ll[i - 1];

    int low = 1, high = R;
    int result = 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (isFeasible(mid, R, X_ll, B, prefix_sum)) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int main() {
    int R, L;
    ll B;
    cin >> R >> L >> B;
    vector<int> X(R);
    for (int i = 0; i < R; ++i) cin >> X[i];
    sort(X.begin(), X.end());
    int max_m = besthub(R, L, X, B);
    cout << max_m << endl;
    return 0;
}

Compilation message (stderr)

ricehub.cpp: In function 'int main()':
ricehub.cpp:53:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
   53 |     sort(X.begin(), X.end());
      |     ^~~~
      |     qsort