Submission #1203694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203694		LucaIlie	Ski 2 (JOI24_ski2)	C++20	86 / 100	734 ms	429440 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];

void simplifyData(int n) {
    vector<int> h;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= n; j++)
            h.push_back(blocks[i].h + j);
    }
    sort(h.begin(), h.end());
    h.resize(unique(h.begin(), h.end()) - h.begin());
    for (int i = 0; i < n; i++) 
        blocks[i].h = lower_bound(h.begin(), h.end(), blocks[i].h) - h.begin();
}

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;
        }
    }

    simplifyData(n);

    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] - (long long)minCost * g);
    }
    for (int h = minH + 1; h <= maxH; h++) {
        int extra = costsByH[h].size();
        for (int g = 0; g <= n; g++) {
            deque<int> dq;
            for (int j = 0; j <= g; j++) {
                while (!dq.empty() && dp[h - 1][j][g] <= dp[h - 1][dq.back()][g])
                    dq.pop_back();
                dq.push_back(j);
            }
            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]);
                dp[h][i][g] = min(dp[h][i][g], dp[h - 1][dq.front()][g]);
                
                if (dq.front() == i - extra)
                    dq.pop_front();
                if (i - extra + g + 1 <= n) {
                    while (!dq.empty() && dp[h - 1][i - extra + g + 1][g] <= dp[h - 1][dq.back()][g])
                        dq.pop_back();
                    dq.push_back(i - extra + g + 1);
                }

                if (i - extra + g <= n) 
                    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] - (long long)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: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 33 / 33
• Subtask 5: 27 / 27
• Subtask 6: 0 / 14