/**
* Quite trivial?
*
* Time Complexity: O(R) (two-pointer, binary search)
* Implementation 1 (Full solution)
*/
#include <bits/stdc++.h>
#include "ricehub.h"
typedef long long ll;
// Calculate the cost of grabbing all rice hubs between a and b, inclusive.
inline ll calc_cost(const std::vector<ll>& prefix_sum, int a, int b) {
int mid = (a + b) / 2, mid_val = prefix_sum[mid + 1] - prefix_sum[mid];
ll c1 = (mid - a + 1) * mid_val - (prefix_sum[mid + 1] - prefix_sum[a]);
ll c2 = (prefix_sum[b + 1] - prefix_sum[mid + 1]) - (b - mid) * mid_val;
return c1 + c2;
}
int besthub(int R, int L, int X[], ll B) {
std::vector<ll> prefix_sum(R + 1);
prefix_sum[0] = 0;
for (int k = 0; k < R; k++)
prefix_sum[k + 1] = prefix_sum[k] + X[k];
int max_rice = 0;
for (int a = 0, b = 0; b < R; a++) {
while (b < R && calc_cost(prefix_sum, a, b) <= B)
b++;
max_rice = std::max(max_rice, b - a);
}
return max_rice;
}
