提出 #58553881

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    ll X;
    cin >> N >> K >> X;
    vector<ll> T(N);
    for (int i = 0; i < N; i++) cin >> T[i];
    vector<ll> S(N + 1);
    for (int i = 0; i < N; i++) S[i + 1] = S[i] + T[i];
    // [l, r) を時刻 t でとるときのコスト
    auto f = [&](ll l, ll r, ll t) -> ll {
        return t * (r - l) - S[r] + S[l];
    };

    // dp[i][j] の定義
    // [0, i) をやった
    // 1 個前の操作が、T[j + i] - X より前
    vector dp(N, vector<ll>(K, 1ll << 60));
    // [hoge, i] をやった直後
    vector<ll> dp2(N, 1ll << 60);
    ll ans = (1ll << 60);
    dp[0][0] = 0;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < K; j++){
            if (i - j < 0) break;
            if (j + 1 != K) chmin(dp[i - j][j + 1], dp[i - j][j]);
            chmin(dp2[i], dp[i - j][j] + f(i - j, i + 1, T[i]));
        }
        int r = i + 1, l;
        ll t = T[i];
        ll cost = dp2[i];
        while (r != N){
            // 一個前のタイミングが t なので、
            // t <= T[r + a] - X となるような a を探したい
            int a = 0;
            while (r + a != N && a != K && t > T[r + a] - X) a++;
            // a があったら、 dp を更新
            if (r + a != N && a != K){
                chmin(dp[r][a], cost);
                // 次に急いでやる範囲は [r, r + a)
                // a = 0 なら、T[r - 1] と T[r] が十分離れていることになる
                if (a == 0){
                    break;
                }
            }
            else{
                // 次に急いでやる範囲は [r, r + K)
                // r + K は N で抑える
                a = min(K, N - r);
            }
            // l, r, t を更新する
            l = r;
            r = r + a;
            t += X;
            // [l, r) を t のタイミングでとる
            cost += f(l, r, t);
        }
        if (r == N) chmin(ans, cost);
    }
    cout << ans << "\n";
}

提出情報

ジャッジ結果