Submission #1239796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239796		The_Samurai	Ski 2 (JOI24_ski2)	C++20	100 / 100	1071 ms	217484 KiB

Main

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second
const ll inf = 1e18;

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

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n; ll k;
    cin >> n >> k;
    vector<pair<ll, ll>> a(n);
    for (auto &[x, y]: a) cin >> x >> y;
    for (auto &[x, y]: a) x++;
    vector<int> ord = {0};
    for (auto &[x, y]: a) ord.emplace_back(x);
    sort(ord.begin(), ord.end());
    for (int i = 1; i < ord.size(); i++) ord[i] = max(ord[i - 1] + 1, ord[i]);
    ord.resize(unique(ord.begin(), ord.end()) - ord.begin());
    auto id = [&](int x) -> int {
        return lower_bound(ord.begin(), ord.end(), x) - ord.begin();
    };

    const int N = ord.size();
    vector<ll> pmn(N + 1, inf);
    for (auto &[x, y]: a) mins(pmn[id(x) + 1], y);
    for (int i = 1; i < N; i++) mins(pmn[i], pmn[i - 1]);
    vector<int> cnt(N);
    for (auto [x, y]: a) cnt[id(x)]++;

    vector<vector<vector<ll>>> dp(N, vector<vector<ll>>(n + 1, vector<ll>(n + 1, inf)));
    dp[0][1][0] = 0;
    for (int h = 1; h < N; h++) {
        for (int fr = 0; fr <= n; fr++) {
            for (int gv = 0; gv < n; gv++) {
                if (dp[h - 1][fr][gv] == inf) continue;
                int tot = gv + cnt[h], fr2 = fr;
                ll sum = dp[h - 1][fr][gv];
                // cout << h << ' ' << fr << ' ' << gv << ' ' << tot << ' ' << sum << endl;
                mins(dp[h][fr][tot], sum + k * tot);
                if (tot >= fr) {
                    mins(dp[h][fr][tot - fr], sum + k * (tot - fr));
                    for (int gv2 = tot - fr - 1; gv2 >= 0; gv2--) {
                        sum = min(inf, sum + pmn[h]);
                        mins(dp[h][tot - gv2][gv2], sum + k * gv2);
                    }
                } else {
                    mins(dp[h][fr][0], sum);
                }
                // for (int gv2 = tot - 1; gv2 >= 0; gv2--) {
                //     if (fr2 > 0) fr2--;
                //     else sum = min(inf, sum + pmn[h]);
                //     mins(dp[h][fr2 + (tot - gv2)][gv2], sum + k * gv2);
                // }
            }
        }
    }
    ll ans = inf;
    for (int i = 0; i <= n; i++) mins(ans, dp[N - 1][i][0]);
    assert(ans < inf);
    cout << ans;
    // cout << ans << '\n';
    // cout << brute(n, k, a) << '\n';
}

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