Submission #1203637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203637		LucaIlie	Ski 2 (JOI24_ski2)	C++20	42 / 100	2101 ms	428560 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct block {
    int h, c;
};

const int MAX_N = 300;
const int MAX_H = 2 * MAX_N + 3;
const long long INF = 1e15;
block blocks[MAX_N + 1];
long long dp[MAX_H + 1][MAX_N + 1][MAX_N + 1];
long long minPref[MAX_N + 1][MAX_N + 1];
vector<int> costsByH[MAX_H + 1];

int main() {
    int n, k;
    long long costInit = 0;

    cin >> n >> k;
    for (int i = 0; i < n; i++) 
        cin >> blocks[i].h >> blocks[i].c;

    sort(blocks, blocks + n, [](block a, block b) {
        if (a.h == b.h)
            return a.c < b.c;
        return a.h < b.h;
    });
    
    for (int i = 1; i < n; i++) {
        if (blocks[i].h == blocks[0].h) {
            blocks[i].h++;
            costInit += k;
        }
    }
    for (int i = 0; i < n; i++) 
        costsByH[blocks[i].h].push_back(blocks[i].c);

    int minH = blocks[0].h, maxH = n + blocks[n - 1].h + 2;

    for (int h = 0; h <= maxH; h++) {
        for (int i = 0; i <= n; i++) {
            for (int g = 0; g <= n; g++)
                dp[h][i][g] = INF;
        }
    }
    dp[minH][1][1] = costInit;

    int minCost = blocks[0].c;
    for (int i = 0; i <= n; i++) {
        minPref[i][0] = dp[minH][i][0];
        for (int g = 1; g <= n; g++)
            minPref[i][g] = min(minPref[i][g - 1], dp[minH][i][g] - minCost * g);
    }
    for (int h = minH + 1; h <= maxH; h++) {
        int extra = costsByH[h].size();
        for (int g = 0; g <= n; g++) {
            for (int i = extra; i <= n; i++) {
                for (int j = 0; j + i - extra <= n && j <= g; j++) 
                    dp[h][i][g] = min(dp[h][i][g], dp[h - 1][i - extra + j][g]);

                if (i - extra + g <= n) {
                    for (int g2 = 0; g2 <= g; g2++)
                        dp[h][i][g] = min(dp[h][i][g], dp[h - 1][i - extra + g][g2] + (long long)minCost * (g - g2));
                    //dp[h][i][g] = min(dp[h][i][g], minPref[i - extra + g][g] + (long long)minCost * g);
                }
                dp[h][i][g] += (long long)k * (i - extra);
                dp[h][i][g] = min(dp[h][i][g], INF);
            }   
        }

        /*
        for (int i = 0; i <= n; i++) {
            for (int g = 0; g <= n; g++)
                printf("%lld ", dp[h - 1][i][g]);
            printf("\n");
        }
        printf("\n");
        */

        for (int c: costsByH[h - 1])
            minCost = min(minCost, c);

        for (int i = 0; i <= n; i++) {
            minPref[i][0] = dp[h][i][0];
            for (int g = 1; g <= n; g++)
                minPref[i][g] = min(minPref[i][g - 1], dp[h][i][g] - minCost * g);
        }
    }

    long long ans = INF;
    for (int g = 0; g <= n; g++)
        ans = min(ans, dp[maxH][0][g]);
    cout << ans << "\n";

    return 0;
}

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