#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int besthub(int RiceCount, int Length, int RiceFields[], long long Budget)
{
int count_before = 0;
int count_after = 0;
ll cost = 0;
int best_count = 1;
for (int i = 1; i < RiceCount; i++)
{
// set the hub at this field
int x = RiceFields[i];
ll distance = RiceFields[i] - RiceFields[i-1];
// account for the prev_index now also having distance
count_before++;
cost += distance * count_before;
cost -= distance * count_after;
if (count_after > 0) {
count_after --;
}
auto add_after = [&](){
while (cost <= Budget && i+count_after < RiceCount-1) {
count_after++;
cost += RiceFields[i+count_after] - x;
}
if (cost > Budget) {
cost -= RiceFields[i+count_after] - x;
count_after--;
}
};
while (
count_before > 0
&& (
cost > Budget
|| (
i+count_after < RiceCount - 1 &&
(x - RiceFields[i-count_before]) > (RiceFields[i+count_after+1] - x)
)
)) {
cost -= x - RiceFields[i-count_before];
count_before--;
add_after();
}
add_after();
int current_count = count_before + count_after + 1;
if (current_count > best_count) {
best_count = current_count;
}
}
return best_count;
}
