IOI '11 P3 - Rice Hub (Standard I/O)

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int R, L; long long B;
    cin >> R >> L >> B;
    vector<int> x(R); vector<long long> xPrefixSum(1+R);
    for (int i = 0; i < R; ++i) cin >> x[i], xPrefixSum[i+1] = xPrefixSum[i] + x[i];
    auto xRangeSum = [&](int l, int r) { // [l, r]
        return xPrefixSum[r+1] - xPrefixSum[l];
    };
    // binary search on answer
    int left = 0, right = R+1;
    while (left+1 < right) {
        int mid = (left + right) / 2;
        // check if mid can be achieved
        bool works = false;
        for (int center = (mid-1)/2; center + mid/2 < R && !works; ++center) {
            int l = center - (mid-1)/2, r = center + mid/2;
            long long a = (long long)(center-l)*x[center] - xRangeSum(l, center-1);
            long long b = xRangeSum(center+1, r) - (long long)(r-center)*x[center];
            if (a+b <= B) works = true;
        }
        if (works) left = mid;
        else right = mid;
    }
    cout << left << endl;
    return 0;
}