Submission #1313567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313567		pvpro	Ski 2 (JOI24_ski2)	C++20	42 / 100	2105 ms	426628 KiB

Main

#ifndef LOCAL
#pragma GCC Optimize("O3,Ofast,unroll-loops")
#pragma GCC Target("bmi,bmi2,avx,avx2")
#endif
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define int ll

#define f first 
#define s second 
#define mp make_pair 
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin() (x).rend()
#define relax(x, y) (x) = min((x), (y));
#ifndef LOCAL
#define endl "\n"
#endif

mt19937 rnd(11);

void solve() {
    int n, k;
	cin >> n >> k;
	vector<pii> a(n);
	int H = 0;
	int mn = 1e9;
	for (auto &x : a) {
		cin >> x.f >> x.s;
		H = max(H, x.f);
		mn = min(mn, x.f);
	}
	H -= mn;
	H = H + n + 3;
	for (auto &x : a) {
		x.f -= mn;
	}
	vector<int> c(H, 1e18);
	vector<int> g(H);
	for (auto &x : a) {
		++g[x.f];
		c[x.f] = min(c[x.f], x.s);
	}
	for (int i = 0; i < H - 1; ++i) {
		c[i + 1] = min(c[i + 1], c[i]);
	}
	int dp[H][n + 1][n + 1];
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j <= n; ++j) {
			for (int k = 0; k <= n; ++k) {
				dp[i][j][k] = 1e18;
			}
		}
	}
	dp[0][1][g[0] - 1] = (g[0] - 1) * k;
	for (int i = 1; i < H; ++i) {
		for (int q = 0; q <= n; ++q) {
			for (int in = 0; in <= n - g[i]; ++in) {
				for (int out = 0; out <= max(0ll, in + g[i] - q); ++out) {
					int r = in + g[i] - out;
					relax(dp[i][max(r, q)][out], dp[i - 1][q][in] + max(r - q, 0ll) * c[i - 1] + k * out);
				}
			}
		}
	}
	int ans = 1e18;
	for (int c = 0; c <= n; ++c) {
		ans = min(ans, dp[H - 1][c][0]);
	}
	cout << ans << endl;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else
        ios::sync_with_stdio(false);
        cin.tie(0);
    #endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 9 / 9
• Subtask 4: 33 / 33
• Subtask 5: 0 / 27
• Subtask 6: 0 / 14