// IOI 2011
// Day 1 Problem 3, Rice Hub
#include <iostream>
#include <ricehub.h>
using namespace std;
/*
* Idea: sliding window on range -
* if less dist take max?
* median is the location of hub
*/
typedef long long ll;
ll psum[100005];
ll cst(int R, int l, int r)
{
if (l == r) return 0;
int mid = (l + r) / 2;
if ((r - l) % 2) return psum[r] - psum[mid] - (psum[mid] - (l ? psum[l - 1] : 0));
else return psum[r] - psum[mid] - (psum[mid - 1] - (l ? psum[l - 1] : 0));
}
// R: number of rice fields
// L: longest dist
// X: all the field's locations
// B: max number spent
// return best r - l + 1
int besthub(int R, int L, int X[], ll B)
{
psum[0] = X[0];
for (int i = 1; i < R; i++)
psum[i] = psum[i - 1] + X[i];
int l = 0, r = 0, ans = 1;
while (r < R)
{
if (cst(R, l, r) <= B) ans = max(ans, r - l + 1);
while (r + 1 < R && cst(R, l, r + 1) <= B)
{
++r;
ans = max(ans, r - l + 1);
}
while (cst(R, l, r) > B)
++l;
++r;
}
return ans;
}
//int main()
//{
// int arr[] = { 1, 4, 10, 11, 14 };
// cout << besthub(5, 20, arr, 18);
// return 0;
//}
