Submission #1272742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272742		hssaan_arif	Ski 2 (JOI24_ski2)	C++20	0 / 100	108 ms	218156 KiB

Main

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

#define endl "\n"
#define pb push_back
#define int long long

const int N = 3e2 + 5, M = 1e9 + 7, LG = 20;

int n , k1 ,H[N] , C[N] , dp[N][N] , c[N][N][N] , h[N][N][N];

void solve(){
    cin >> n >> k1;
    for (int i = 1 ; i <= n ; i++){
        cin >> H[i] >> C[i];
    }
    dp[1][1] = 0;
    c[1][1][1] = 1;
    h[1][1][1] = H[1];
    for (int i = 2 ; i <= n ; i++){
        for (int j = 1 ; j < i ; j++){
            dp[i][j] = dp[i-1][j];
            int ind = -1 , cs = 1e18;
            for (int k = 1 ; k < i ; k++){
                if (h[i-1][j][k] < H[i]){
                    if (c[i-1][j][k]){
                        if (cs){
                            cs = 0;
                            ind = k;
                        }
                    }else{
                        if (cs > C[k]){
                            ind = k;
                            cs = C[k];
                        }
                    }
                }else{
                    int lp = (h[i-1][j][k] - H[i]  + 1) * k1;
                    if (c[i-1][j][k]){
                        if (cs > lp){
                            cs = lp;
                            ind = k;
                        }
                    }else{
                        if (cs > C[k] + lp){
                            ind = k;
                            cs = C[k] + lp;
                        }
                    }
                }
            }
            
            c[i][j][i] = 1;
            c[i][j][ind] = c[i-1][j][ind];
            if (c[i-1][j][ind]){
                c[i][j][ind] = 0;
                c[i-1][j][ind] = 0;
            }

            h[i][j][i] = H[i];
            h[i][j][ind] = h[i-1][j][ind];
            if (h[i-1][j][ind] > H[i]){
                h[i][j][i] = h[i-1][j][ind] + 1;
            }
            dp[i][j] += cs;
        }
        int op[i+2] = {};
        op[i] = 0;
        h[i][i][i] = H[i];
        c[i][i][i] = 1;
        for (int j = i-1 ; j > 0 ; j--){
            h[i][i][j] = H[j];
            c[i][i][j] = 1;
            int ind = -1 , cs = 1e18;
            for (int k = j+1 ; k <= i ; k++){
                if (H[j] > h[i][i][k]){
                    if (c[i][i][k]){
                        if (cs > op[k]){
                            cs = op[k];
                            ind = k;
                        }
                    }else{
                        if (cs > C[k] + op[k]){
                            cs = C[k] + op[k];
                            ind = k;
                        }
                    }
                }else{
                    int lp = (h[i][i][k] - H[j] + 1) * k1;
                    if (c[i][i][k]){
                        if (cs > lp + op[k]){
                            cs = lp + op[k];
                            ind = k;
                        }
                    }else{
                        if (cs > C[k] + lp + op[k]){
                            ind = k;
                            cs = C[k] + lp + op[k];
                        }
                    }
                }
            }

            if (c[i][i][ind]){
                c[i][i][ind] = 0;
            }
            if (h[i][i][ind] > H[j]){
                h[i][i][j] = h[i][i][ind] + 1;
            }
            op[j] = cs;
            dp[i][i] += op[j];
        }
    }
    int ans = 1e18;
    for (int i = 1 ; i <= n ; i++){
        // cout << dp[n][i] << endl;
        ans = min(dp[n][i] , ans);
    }
    cout << ans << endl;
}

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

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