Submission #1004899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004899		PurpleCrayon	Ski 2 (JOI24_ski2)	C++17	86 / 100	2050 ms	446800 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e2+10, MOD = 1e9+7;
const ll INF = 1e18+10;

// prefix minimums don't move (well except when deciding the starting point but that's easy to deal with)
// the costs of the rest don't matter
// you only pay a cost when you stack more at some index than previously stacked
// only relevant positions are index positions, prefix minimum positions + 1
// dp[position][how much i've stacked before][number i'm dragging along]
// at each position consider stacking more (transition cost is new_stacked * my_cost), thankfully not CHT
// then you always just place as many as you've stacked before, make sure to pick up new ones before transitioning

ll dp[2 * N][N][N];

ll mul(ll a, ll b) {
    __int128 ans = (__int128) a * b;
    if (ans >= INF) return INF;
    return ans;
}

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

void solve() {
    int n; ll K; cin >> n >> K;
    vector<pair<ll, ll>> a(n); for (auto& [h, c] : a) cin >> h >> c;
    sort(a.begin(), a.end());

    vector<pair<ll, ll>> mns, rest;
    
    int mn = MOD;
    for (int i = 0; i < n; i++) {
        if (a[i].second < mn) {
            mns.push_back(a[i]);
            mn = a[i].second;
        } else {
            rest.push_back(a[i]);
        }
    }

    vector<ll> use;
    for (auto [x, c] : a) {
        use.push_back(x);
        use.push_back(x + 1);
    }

    sort(use.begin(), use.end());
    use.resize(unique(use.begin(), use.end()) - use.begin());

    assert(use[0] == mns[0].first);
    use.erase(use.begin());

    for (int i = 0; i <= sz(use); i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                dp[i][j][k] = INF;
            }
        }
    }

    auto idx = [&](ll x) {
        return lower_bound(use.begin(), use.end(), x) - use.begin();
    };

    auto my_cost = [&](ll x) {
        return mns[lower_bound(mns.begin(), mns.end(), make_pair(x, -1LL)) - mns.begin() - 1].second;
    };

    for (auto [x, c] : mns) {
        ll sum = 0;
        int cnt = 0;
        for (auto [he, _] : mns) if (he < x)
            sum += (x + 1 - he) * K, cnt++, sum = min(sum, INF);

        for (auto [he, _] : rest) if (he <= x)
            sum += (x + 1 - he) * K, cnt++, sum = min(sum, INF);

        // cerr << "base: " << idx(x + 1) << ' ' << 1 << ' ' << cnt << ' ' << sum << endl;
        smin(dp[idx(x + 1)][1][cnt], sum);
    }

    /*
    cerr << "use: ";
    for (int x : use) cerr << x << ' ';
    cerr << endl;
    */


    vector<bool> spec(sz(use)); // can stack one less
    for (int i = 0; i < sz(use); i++) {
        for (auto [x, _] : mns) if (x == use[i])
            spec[i] = 1;
    }

    for (int i = 0; i < sz(use); i++) {
        // cerr << "at: " << i << endl;
        ll cur_cost = my_cost(use[i]);
        ll cnt = (i < sz(use)-1 ? use[i+1] - use[i] : MOD);

        int extra = 0;
        for (auto [x, _] : rest) if (x == use[i]) extra++;
        // cerr << cur_cost << ' ' << cnt << ' ' << extra << endl;

        for (int j = 1; j <= n; j++) {
            for (int k = n; k >= 0; k--) {
                if (k >= extra) dp[i][j][k] = dp[i][j][k - extra];
                else dp[i][j][k] = INF;
            }
        }

        vector<ll> best(n + 1, INF);
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                // cerr << "> " << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k] << endl;
                smin(dp[i][j][k], best[k] + j * cur_cost);
                if (dp[i][j][k] == INF) continue;
                smin(best[k], dp[i][j][k] - j * cur_cost);
                /*
                for (int nj = j + 1; nj <= n; nj++) {
                    smin(dp[i][nj][k], dp[i][j][k] + (nj - j) * cur_cost);
                }
                */


                ll sum = 0;
                ll left = k;
                smin(dp[i+1][j][left], dp[i][j][k] + sum + mul(left * cnt, K));
                for (ll me = 0; me < cnt && left > 0; me++) {
                    ll cur_use = min(left, (long long) j - (me == 0 && spec[i]));
                    for (ll act = 0; act <= cur_use; act++) {
                        smin(dp[i+1][j][left - act], dp[i][j][k] + sum + mul(act * me, K) + mul((left - act) * cnt, K));
                    }

                    sum += cur_use * me * K;
                    left -= cur_use;
                }
            }
        }
    }

    ll ans = INF;
    for (int j = 1; j <= n; j++) {
        smin(ans, dp[sz(use)][j][0]);
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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