| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1272395 | btkhg | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
long long besthub(int R, long long L, vector<long long> X, long long B) {
// X is sorted non-decreasing as per problem statement.
vector<long long> P(R + 1, 0); // prefix sums, P[0]=0, P[k]=sum of X[0..k-1]
for (int i = 0; i < R; ++i) P[i + 1] = P[i] + X[i];
auto costWindow = [&](int i, int j) -> long long {
int m = (i + j) / 2; // median index
long long xm = X[m];
// Left side cost: sum_{k=i..m-1} (xm - X[k]) = xm*(m-i) - (P[m]-P[i])
long long leftCost = xm * (m - i) - (P[m] - P[i]);
// Right side cost: sum_{k=m+1..j} (X[k] - xm) = (P[j+1]-P[m+1]) - xm*(j-m)
long long rightCost = (P[j + 1] - P[m + 1]) - xm * (j - m);
return leftCost + rightCost;
};
long long ans = 1;
int i = 0;
for (int j = 0; j < R; ++j) {
// Expand right end to j, and shrink from left while over budget
while (i <= j && costWindow(i, j) > B) ++i;
ans = max(ans, (long long)(j - i + 1));
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int R; long long L, B;
if (!(cin >> R >> L >> B)) return 0;
vector<long long> X(R);
for (int i = 0; i < R; ++i) cin >> X[i];
cout << besthub(R, L, X, B) << "\n";
return 0;
}