#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 600 + 10,
MAX = 1'000'000'000'000'000'000;
int n, k;
int h[N], c[N];
int minC[N], cnt[N];
int f[N][N][N];
inline void getMin(auto& x, const auto& y) { x = min(x, y); }
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> h[i] >> c[i];
vector<int> allH;
for (int i = 1; i <= n; ++i) allH.push_back(h[i]), allH.push_back(h[i] + 1);
{ // discrete
sort(allH.begin(), allH.end());
allH.erase(unique(allH.begin(), allH.end()), allH.end());
}
const int sz = allH.size();
fill(minC, minC + sz + 1, MAX);
for (int i = 1; i <= n; ++i) {
int itH = lower_bound(allH.begin(), allH.end(), h[i]) - allH.begin();
getMin(minC[itH], c[i]);
cnt[itH] += 1;
}
auto cal = [&](int m, int w, int num) {
int k = min(num / m, w);
return k * (k - 1) / 2 * m + k * (num - k * m);
};
memset(f, 14, sizeof f);
f[0][1][0] = 0;
int mn = MAX;
for (int i = 0; i < sz; ++i) {
int w = (i == sz - 1 ? n : allH[i + 1] - allH[i]);
for (int j = 1; j <= n; ++j) {
for (int t = 0; t <= n; ++t) {
int cur = f[i][j][t];
if (cur >= MAX) continue;
if (j < n) getMin(f[i][j + 1][t], cur + mn);
int num = t + cnt[i];
getMin(f[i + 1][j][max(0ll, num - j * w)], cur + 1ll * k * cal(j, w, num));
}
}
mn = min(mn, minC[i]);
}
int answer = MAX;
for (int i = 1; i <= n; ++i) getMin(answer, f[sz][i][0]);
cout << answer << "\n";
}
Compilation message (stderr)
Main.cpp:15:20: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
15 | inline void getMin(auto& x, const auto& y) { x = min(x, y); }
| ^~~~
Main.cpp:15:35: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
15 | inline void getMin(auto& x, const auto& y) { x = min(x, y); }
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |