#include "ricehub.h"
#include <algorithm>
#include <cassert>
#include <iterator>
#include <vector>
using namespace std;
using ull = unsigned long long;
vector<ull> sp;
vector<uint> x;
// 1 2 10
// 1 - 10 + 2 - 10
// 1 + 2 - 10 * 2
// t = {1, 2, 10}
// 0 1 2
// sum do 2 = sp[2]
ull get_ss(uint b, uint e) {
ull count = e - b;
ull sum_i = sp[e] - sp[b];
ull tot_sum = count * x[e];
ull sum_s = tot_sum - sum_i;
return sum_s;
}
ull get_sp(uint b, uint e) {
// 1 2 5 6
// 2 - 1 + 5 - 1 + 6 - 1
// 2 + 5 + 6 - 3 * 1
ull count = e - b;
ull sum_i = sp[e + 1] - sp[b + 1];
ull tot_sum = count * x[b];
ull sum_s = sum_i - tot_sum;
return sum_s;
}
ull get_dst_ss(uint b, uint v, uint beg_i) {
ull dst = get_ss(b, beg_i);
ull count = beg_i - b + 1;
return dst + count * (v - x[beg_i]);
}
ull get_dst_sp(uint e, uint v, uint beg_i) {
ull dst = get_sp(beg_i, e);
ull count = e - beg_i + 1;
return dst + count * (x[beg_i] - v);
}
ull get_dst(uint v, uint b, uint e) {
const vector<uint>::iterator beg_it = lower_bound(x.begin(), x.end(), v);
uint beg_i = distance(x.begin(), beg_it);
// beg_i
// A B v C D E
// --- dsta
// dstb------
ull dsta = (beg_i > 0 ? get_dst_ss(b, v, beg_i - 1) : 0);
ull dstb = (beg_i < x.size() ? get_dst_sp(e, v, beg_i) : 0);
return dsta + dstb;
}
pair<uint, ull> get_best(uint b, uint e) {
uint mid = (sp[e + 1] - sp[b]) / (e - b + 1);
ull dst1 = get_dst(mid, b, e);
ull dst2 = get_dst(mid + 1, b, e);
if (dst1 < dst2) {
return {mid, dst1};
} else {
return {mid + 1, dst2};
}
}
bool check(uint k, ull b) {
for (uint i = 0; i + k <= x.size(); i++) {
if (get_best(i, i + k - 1).second <= b) {
return true;
}
}
return false;
}
uint slv(uint r, ull b) {
sp.resize(r + 1);
sp[0] = 0;
for (uint i = 0; i < r; i++) {
sp[i + 1] = sp[i] + x[i];
}
uint s = 0, e = r;
while (s < e) {
const uint mid = (s + e + 1) / 2;
if (check(mid, b)) {
s = mid;
} else {
e = mid - 1;
}
}
return s;
}
int besthub(int R, int L, int X[], long long B) {
x.resize(R);
copy(X, X + R, x.begin());
(void)L;
return slv(R, B);
}
