#include <bits/stdc++.h>
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
/usr/bin/ld: /tmp/ccj682tn.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccjtKgDk.o:ricehub.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccj682tn.o: in function `main':
grader.cpp:(.text.startup+0xae): undefined reference to `besthub(int, int, int*, long long)'
collect2: error: ld returned 1 exit status
