#include <bits/stdc++.h> #include "ricehub.h" using namespace std; const int N = 1e5 + 5; int pref[N]; vector<int> x; int cost(int l, int r){ int idx = (l + r) / 2, centre = x[(l + r) / 2]; int sub = pref[idx], add = pref[r] - pref[idx]; if (l != 0) sub -= pref[l - 1]; return ((idx - l + 1) * centre - sub + add - (r - idx) * centre); } int besthub(int R, int L, int X[], long long B) { int l = 0, r = R + 1, s = 0; for (int i = 0; i < R; i++){ x.push_back(X[i]); s += X[i]; pref[i] = s; } pref[R] = pref[R - 1]; while (r - l > 1){ int m = (l + r) / 2; int ans = 1e9; for (int i = m - 1; i < R; i++){ ans = min(ans, cost(i - m + 1, i)); } if (ans <= B) l = m; else r = m; } return l; }