#include "ricehub.h"
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <fstream>
using namespace std;
int besthub(int R, int L, int X[], long long B)
{
long long left_best = 0;
long long right_best = 0;
long long current_cost = 0;
long long current_field = 0;
long long current_max = 1;
while (current_cost <= B){
if (right_best == R - 1){
break;
}
if (X[right_best + 1] - X[0] + current_cost > B){
break;
}
right_best++;
current_cost += X[right_best] - X[0];
current_max++;
}
long long best = current_max;
while (current_field != R - 1){
long long distance_moved = X[current_field + 1] - X[current_field];
long long to_right = right_best - current_field;
long long to_left = current_field - left_best + 1;
current_cost += to_left * distance_moved;
current_cost -= to_right * distance_moved;
if (current_field == right_best){
right_best++;
current_max++;
}
current_field++;
while (current_cost > B){
current_cost -= (X[current_field] - X[left_best]);
current_max--;
left_best++;
}
while (right_best != R - 1){
if (current_cost + X[right_best + 1] - X[current_field] <= B){
current_cost += (X[right_best + 1] - X[current_field]);
right_best++;
current_max++;
} else {
if (X[current_field] - X[left_best] > X[right_best] - X[current_field]){
current_cost -= (X[current_field] - X[left_best]);
current_cost += (X[right_best + 1] - X[current_field]);
right_best++;
left_best++;
} else {
break;
}
}
}
best = max(current_max, best);
}
//cout << X[0] << ' ' << X[1] << ' ' << X[2] << endl;
//cout << best << ' ' << current_cost << ' ' << right_best << ' ' << B << endl;
return best;
}
