Submission #1203608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203608		LucaIlie	Ski 2 (JOI24_ski2)	C++20	0 / 100	479 ms	428080 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 int MAX_COST = 1e9;
const long long INF = 1e15;
block blocks[MAX_N + 1];
long long dp[MAX_H + 1][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;

    priority_queue<int> pq;
    int minCost = MAX_COST;
    for (int h = minH; h < maxH; h++) {
        int extra = costsByH[h + 1].size();
        for (int g = 0; g <= n; g++) {
            for (int i = 0; i <= n; i++) {
                for (int j = 0; j <= 0; j++)
                    dp[h + 1][i - j + extra][max(g - j, 0) + j] = min(dp[h + 1][i - j + extra][max(g - j, 0) + j], 
                            dp[h][i][g] + (long long)k * (i - j) + (long long)minCost * max(j - g, 0));
            }   
        }

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

        for (int c: costsByH[h])
            pq.push(-c);
        if (!pq.empty()) {
            minCost = min(minCost, -pq.top());
            pq.pop();
        }
    }

    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: 0 / 9
• Subtask 4: 0 / 33
• Subtask 5: 0 / 27
• Subtask 6: 0 / 14