#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) { x.resize(r); 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) { copy(X, X + R, x.begin()); (void)L; return slv(R, B); }