题解 p1485 火枪打怪

using namespace std;
typedef long long ll;
ll p, k, n;
ll a[1000010], tot[1000010];
struct  {
    ll cnt, cnti, cnti2;
    inline void clear() {
        cnt = cnti = cnti2 = 0;
    }
    inline void add(ll i, ll k) {
        cnt += k;
        cnti += k * i;
        cnti2 += k * i * i;
    }
    inline ll get(ll i) {
        return (p - i * i) * cnt + 2 * cnti * i - cnti2;
    }
} d;
inline ll check() {
    ll maxdis = 0, sum = 0;
    d.clear();
    for(; maxdis <= n && maxdis * maxdis <= p; maxdis++);
    
    for(ll i = n; i > 0; i--) {
        if(i + maxdis <= n) d.add(i + maxdis, -tot[i + maxdis]);
        ll rest = a[i] - d.get(i);
        if(rest < 0) tot[i] = 0;
        else tot[i] = rest / p + 1;
        d.add(i, tot[i]);
        sum += tot[i];
    }
    // for(int i = 1; i <= n; i++) printf("%lld ", tot[i]);
    // puts("");
    return sum <= k;
}
int main() {
    scanf("%lld%lld", &n, &k);
    for(ll i = 1; i <= n; i++) scanf("%lld", a + i);
    ll ans, l = 1, r = 3e11;
    while(l <= r) {
        p = (l + r) >> 1;
        if(check()) ans = p, r = p - 1;
        else l = p + 1;
    }
    return cout << ans << endl, 0;
}