제출 #1203694

#제출 시각아이디문제언어결과실행 시간메모리
1203694LucaIlieSki 2 (JOI24_ski2)C++20
86 / 100
734 ms429440 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...