LC2528

class Solution {
    using ll = long long;
    bool check(const vector<int>& st, ll pcnt, int r, int k) {
        int span = r * 2 + 1;
        int n = st.size();
        vector<ll> diff(n + 1);
        for (int i = 0; i < n; ++i) {
            int lb = max(0, i - r);
            int ub = min(n, i + r + 1);
            diff[lb] += st[i];
            diff[ub] -= st[i];
        }

        ll acc = 0, cost = 0;
        for (int i = 0; i < n; ++i) {
            acc += diff[i];
            if (acc < pcnt) {
                ll delta = pcnt - acc;
                diff[i] += delta;
                acc += delta;

                int ub = min(i + span, n);
                diff[ub] -= delta;
                cost += delta;

                if (cost > k) return false;
            }
        }
        return cost <= k;
    }
public:
    long long maxPower(vector<int>& stations, int r, int k) {
        int span = 2 * r + 1;
        ll lb = 0, cnt = 1e15, it, step;
        while(cnt) {
            it = lb, step = cnt / 2, it += step;
            if (check(stations, it, r, k)) {
                lb = it + 1;
                cnt -= step + 1;
            } else cnt = step;
        }
        return lb - 1;
    }
};