Submission #58494784

---

Source Code Expand

// O(N^2)

#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>

constexpr long long cost_inf = std::numeric_limits<long long>::max() / 2;

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

    int n, k;
    long long x;
    std::cin >> n >> k >> x;

    std::vector<long long> t(n);
    for (auto& e : t) std::cin >> e;

    const long long t_inf = t.back() + n * x;
    // sentinel
    t.push_back(t_inf);

    std::vector<long long> dp(n + 1, cost_inf);
    dp[n] = 0;

    std::vector f(n + 1, std::vector<long long>(k + 1, cost_inf));
    f[n][0] = 0;
    for (int i = n - 1; i >= 0; --i) {
        for (int num = std::min(k, n - i) - 1; num >= 0; --num) {
            f[i][num] = std::min(f[i][num + 1], t[i + num + 1] * (num + 1) + dp[i + num + 1]);
        }
        int l = i, r = i;
        long long cost = 0;
        for (int p = 1;; ++p) {
            const long long s = t[i] + p * x;
            while (r < n and t[r + 1] <= s) ++r;
            const int max_num = std::min(r - l, k);
            dp[i] = std::min(dp[i], cost + f[l][max_num]);
            if (max_num == 0) break;
            cost += max_num * s;
            l += max_num;
        }
    }
    long long min_cost = cost_inf;
    for (int num = 1; num <= k; ++num) {
        min_cost = std::min(min_cost, t[num - 1] * num + dp[num - 1]);
    }
    std::cout << min_cost - std::accumulate(t.begin(), t.end(), 0LL) << '\n';
}

Submission Info

Judge Result