Submission #978204

#	Time	Username	Problem	Language	Result	Execution time	Memory
978204		model_code	Ski 2 (JOI24_ski2)	C++17	100 / 100	246 ms	433132 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 1LL << 60;

void chmin(ll &a, ll b) { a = min(a, b); }

// [0] * m + [1] * m + ... + [w-1] * m + [w] * inf ã®å…ˆé ­ num é …ã®å’Œ
int f(int m, int w, int num) {
    int k = min(num / m, w);
    return k * (k - 1) / 2 * m + k * (num - k * m);
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n), c(n), hs;
    for (int i = 0; i < n; i++) {
        cin >> h[i] >> c[i];
        hs.push_back(h[i]);
        hs.push_back(h[i] + 1);
    }
    sort(hs.begin(), hs.end());
    hs.erase(unique(hs.begin(), hs.end()), hs.end());
    int sz = hs.size();
    vector<int> cnt(sz);
    vector<ll> min_c(sz, INF);
    for (int i = 0; i < n; i++) {
        int p = lower_bound(hs.begin(), hs.end(), h[i]) - hs.begin();
        ++cnt[p];
        chmin(min_c[p], c[i]);
    }
    vector dp(sz + 1, vector(n + 1, vector<ll>(n + 1, INF)));
    dp[0][1][0] = 0;
    ll mn = INF;
    for (int i = 0; i < sz; i++) {
        int w = (i + 1 < sz ? min(n, hs[i + 1] - hs[i]) : n);
        for (int m = 1; m <= n; m++) {
            for (int r = 0; r <= n; r++) {
                ll now = dp[i][m][r];
                if (now == INF) continue;
                if (m < n) chmin(dp[i][m + 1][r], now + mn);
                int num = r + cnt[i];
                chmin(dp[i + 1][m][max(num - m * w, 0)], now + (ll) k * f(m, w, num));
            }
        }
        chmin(mn, min_c[i]);
    }
    ll ans = INF;
    for (int m = 1; m <= n; m++) chmin(ans, dp[sz][m][0]);
    cout << ans << endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 33 / 33
• Subtask 5: 27 / 27
• Subtask 6: 14 / 14