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