Spenser's Big Announcement

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    int n, l;
    10    ll s; cin >> n >> l >> s;
    11    vector<ll> v(n);
    12    ll sum = 0;
    13    for (int i = 0; i < n; i++) {
    14        cin >> v[i];
    15        sum += v[i];
    16    }
    17    ll lo = 0, hi = sum + (n - 1) * s;
    18    auto check = [&] (ll w) {
    19        int indx = 0;
    20        for (int i = 0; i < l && indx < v.size(); i++) {
    21            ll cur = w;
    22            while (indx < v.size() && cur >= v[indx]) {
    23                if (cur == w) {
    24                    cur -= v[indx];
    25                    indx++;
    26                } else {
    27                    if (cur >= v[indx] + s) {
    28                        cur -= v[indx] + s;
    29                        indx++;
    30                    } else {
    31                        break;
    32                    }
    33                }
    34            }
    35        }
    36        return indx == v.size();
    37    };
    38    ll ans = INF;
    39    while (lo <= hi) {
    40        ll mid = lo + (hi - lo) / 2;
    41        int res = check(mid);
    42        if (res) {
    43            ans = min(ans, mid);
    44            hi = mid - 1;
    45        } else {
    46            lo = mid + 1;
    47        }
    48    }
    49    cout << ans << '\n';
    50    return 0;
    51}