제출 #1127789

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127789		fzyzzz_z	Ski 2 (JOI24_ski2)	C++20	100 / 100	887 ms	1864 KiB

Main

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

using ll = long long;

const int N = 301; 
const ll inf = 1e18; 


inline void upd(ll & x, ll y) {
    if (x > y) x = y; 
}

ll dp[N][N]; 
ll ndp[N][N];  

void reset() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            ndp[i][j] = inf; 
        }
    }
}
void fini() {
    for (int i = 0; i < N; ++i) {
        for (int j = N - 1; j >= 0; --j) {
            dp[i][j] = ndp[i][j]; 

            // if (i) upd(dp[i][j], dp[i - 1][j]); 
            // if (j + 1 < N) upd(dp[i][j], dp[i][j + 1]); 
        }
    }
}
void copy() {
    for (int i = 0; i < N; ++i) {
        for (int j = N - 1; j >= 0; --j) {
            ndp[i][j] = dp[i][j]; 
        }
    }
}
void print() {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cout << (dp[i][j] == inf ? -1 : dp[i][j]) << " \n"[j + 1 == N]; 
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            dp[i][j] = ndp[i][j] = inf; 
        }
    }
    int n; 
    ll k; 
    cin >> n >> k; 
    vector<pair<int, int>> a(n); 
    vector<int> v;
    for (auto & [x, y]: a) { // height, cost 
        cin >> x >> y; 
        v.push_back(x); 
    }

    if (n == 1) {
        cout << 0 << '\n'; 
        exit(0); 
    }

    sort(v.begin(), v.end()); 
    for (int i = 1; i < n; ++i) {
        while (v[i] <= v[i - 1]) v[i]++; 
    }
    vector<int> cnt(n, 0); 
    vector<ll> cost(n, inf); 
    for (auto [x, y]: a) {
        for (int i = 0; i < n; ++i) {
            if (v[i] == x) {
                cnt[i]++; 
                upd(cost[i], y); 
            }
        }
    }

    
    // manually compute dp for first thing 
    dp[0][1] = k * (cnt[0] - 1); 
    cnt[1] += cnt[0] - 1; 


    ll best = cost[0]; 
    for (int i = 1; i < n; ++i) {
        // cout << cnt[i] << "\n";
        if (cnt[i]) {
            reset(); 
            for (int x = 0; x <= n; ++x) {
                for (int y = 0; y <= n; ++y) {
                    if (x + cnt[i] <= n) {
                        upd(ndp[x + cnt[i]][y], dp[x][y]); 
                    }
                }

            }
            fini(); 
        }

        // cout << "WTf\n";
        // print();

        reset(); 
        for (int x = 0; x <= n; ++x) {
            for (int y = 0; y <= n; ++y) { // go to next 
                if (dp[x][y] == inf) continue; 
                for (int z = 0;; ++z) {
                    // if (x - y - z < 0 || y + z > n) break;
                    if (y + z > n) break;
                    if (x - y < 0 && z) break;
                    upd(ndp[max(0LL, (ll)x - y - z)][y + z], dp[x][y] + best * z + k * max(0LL, (ll)x - y - z)); 
                }
            }
        }
        fini(); 
        best = min(best, cost[i]);

        // cout << "? " << best << " " << i << '\n';
        // print();  
    }

    ll ans = inf; 
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == 0) ans = min(ans, dp[i][j]); 
        }
    }
    cout << ans << '\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