| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1004879 | PurpleCrayon | Ski 2 (JOI24_ski2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e2+10, MOD = 1e9+7;
const ll INF = 1e18+10;
// prefix minimums don't move (well except when deciding the starting point but that's easy to deal with)
// the costs of the rest don't matter
// you only pay a cost when you stack more at some index than previously stacked
// only relevant positions are index positions, prefix minimum positions + 1
// dp[position][how much i've stacked before][number i'm dragging along]
// at each position consider stacking more (transition cost is new_stacked * my_cost), thankfully not CHT
// then you always just place as many as you've stacked before, make sure to pick up new ones before transitioning
ll dp[2 * N][N][N];
void smin(ll& a, ll b) {
a = min(a, b);
}
void solve() {
int n; ll K; cin >> n >> K;
vector<pair<int, int>> a(n); for (auto& [h, c] : a) cin >> h >> c;
sort(a.begin(), a.end());
vector<pair<int, int>> mns, rest;
int mn = MOD;
for (int i = 0; i < n; i++) {
if (a[i].second < mn) {
mns.push_back(a[i]);
mn = a[i].second;
} else {
rest.push_back(a[i]);
}
}
vector<int> use;
for (auto [x, c] : a) {
use.push_back(x);
use.push_back(x + 1);
}
sort(use.begin(), use.end());
use.resize(unique(use.begin(), use.end()) - use.begin());
assert(use[0] == mns[0].first);
use.erase(use.begin());
for (int i = 0; i <= sz(use); i++) {
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= n; k++) {
dp[i][j][k] = INF;
}
}
}
auto idx = [&](int x) {
return lower_bound(use.begin(), use.end(), x) - use.begin();
};
auto my_cost = [&](int x) {
return mns[lower_bound(mns.begin(), mns.end(), make_pair(x, -1)) - mns.begin() - 1].second;
};
for (auto [x, c] : mns) {
ll sum = 0;
int cnt = 0;
for (auto [he, _] : mns) if (he < x)
sum += (x + 1 - he) * K, cnt++;
for (auto [he, _] : rest) if (he <= x)
sum += (x + 1 - he) * K, cnt++;
// cerr << "base: " << idx(x + 1) << ' ' << 1 << ' ' << cnt << ' ' << sum << endl;
smin(dp[idx(x + 1)][1][cnt], sum);
}
/*
cerr << "use: ";
for (int x : use) cerr << x << ' ';
cerr << endl;
*/
vector<bool> spec(sz(use)); // can stack one less
for (int i = 0; i < sz(use); i++) {
for (auto [x, _] : mns) if (x == use[i])
spec[i] = 1;
}
for (int i = 0; i < sz(use); i++) {
// cerr << "at: " << i << endl;
ll cur_cost = my_cost(use[i]);
ll cnt = (i < sz(use)-1 ? use[i+1] - use[i] : MOD);
int extra = 0;
for (auto [x, _] : rest) if (x == use[i]) extra++;
// cerr << cur_cost << ' ' << cnt << ' ' << extra << endl;
for (int j = 1; j <= n; j++) {
for (int k = n; k >= 0; k--) {
if (k >= extra) dp[i][j][k] = dp[i][j][k - extra];
else dp[i][j][k] = INF;
}
}
vector<ll> best(n + 1, INF);
for (int j = 1; j <= n; j++) {
for (int k = 0; k <= n; k++) {
// cerr << "> " << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k] << endl;
smin(dp[i][j][k], best[k] + j * cur_cost);
if (dp[i][j][k] == INF) continue;
smin(best[k], dp[i][j][k] - j * cur_cost);
/*
for (int nj = j + 1; nj <= n; nj++) {
smin(dp[i][nj][k], dp[i][j][k] + (nj - j) * cur_cost);
}
*/
ll sum = 0;
ll left = k;
smin(dp[i+1][j][left], dp[i][j][k] + sum + left * cnt * K);
for (int me = 0; me < cnt && left > 0; me++) {
ll cur_use = min(left, j - (me == 0 && spec[i]));
for (ll act = 0; act <= cur_use; act++) {
smin(dp[i+1][j][left - act], dp[i][j][k] + sum + act * me * K + (left - act) * cnt * K);
}
sum += cur_use * me * K;
left -= cur_use;
}
}
}
}
ll ans = INF;
for (int j = 1; j <= n; j++) {
smin(ans, dp[sz(use)][j][0]);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int T = 1;
// cin >> T;
while (T--) solve();
}