Submission #983497

#	Time	Username	Problem	Language	Result	Execution time	Memory
983497		box	Ski 2 (JOI24_ski2)	C++17	100 / 100	444 ms	3144 KiB

Main

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

#define sz(v) int(std::size(v))
#define FOR(i,a,b) for (int i = a; i < b; ++i)
#define ROF(i,a,b) for (int i = b-1; i >= a; --i)
typedef long long i64;
typedef vector<int> vi;

const i64 INF = 1e18;

template<class T> void chmin(T &x, T y) {
    x = min(x, y);
}

int N; i64 K;
vi H, C;

void setup() {
    cin >> N >> K;
    H.resize(N), C.resize(N);
    FOR(i,0,N) cin >> H[i] >> C[i];
}

i64 S(i64 N) { return N*(N+1)/2; }

void solve() {
    map<int, int> num, mnC;
    vi h;
    FOR(i,0,N) {
        ++num[H[i]];
        if (!mnC.count(H[i])) mnC[H[i]] = C[i];
        else chmin(mnC[H[i]], C[i]);
        h.push_back(H[i]), h.push_back(H[i]+1), h.push_back(H[i]+2);
    }
    sort(begin(h), end(h)), h.erase(unique(begin(h), end(h)), end(h));
    vector dp(N+1, vector(N+1, INF)), ndp(N+1, vector(N+1, INF));
    int mn = mnC[h.at(0)];
    dp[1][num[h.at(0)]-1] = 0;
    FOR(t,1,sz(h)) {
        int c = num[h[t]];
        ndp = vector(N+1, vector(N+1, INF));
        FOR(i,0,N+1) FOR(j,0,N+1) if (dp[i][j] < INF)
            chmin(ndp[i][max(0, j+c-i)], dp[i][j]+j*K);
        FOR(i,1,N+1) FOR(j,0,N) chmin(ndp[i][j], ndp[i-1][j+1]+mn);
        dp = ndp;
        ndp = vector(N+1, vector(N+1, INF));
        if (mnC.count(h[t])) chmin(mn, mnC[h[t]]);
        i64 l = t+1 < sz(h) ? h[t+1]-h[t]-1 : i64(1e14);
        FOR(i,0,N+1) FOR(j,0,N+1) if (dp[i][j] < INF) {
            if (j-l*i >= 0) chmin(ndp[i][j-l*i], dp[i][j] + K * (S(l)*i + l*(j-l*i)));
            else chmin(ndp[i][0], dp[i][j] + K * (S(j/i)*i + (j%i)*(j/i+1)));
        }
        dp = ndp;
    }
    i64 ans = INF;
    FOR(j,1,N+1) chmin(ans, dp[j][0]);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    setup();
    solve();
}

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