Submission #984789

#	Time	Username	Problem	Language	Result	Execution time	Memory
984789		pavement	Ski 2 (JOI24_ski2)	C++17	86 / 100	530 ms	443268 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;
using ll = long long;

#define mp make_pair
#define pb push_back
#define eb emplace_back

int N, K, H[605], C[605];
ll dp[605][305][305];
ii min_C[605], pref_min_C[605];
vector<int> vec[605];
vector<ll> arr[605];
vector<tuple<int, int, ll*> > queries[605];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 0; i <= 600; i++) {
		pref_min_C[i] = min_C[i] = mp((int)2e9, -1);
	}
	for (int i = 1; i <= N; i++) {
		cin >> H[i] >> C[i];
		vec[H[i]].pb(C[i]);
		min_C[H[i]] = min(min_C[H[i]], mp(C[i], i));
	}
	pref_min_C[0] = min_C[0];
	for (int i = 1; i <= 600; i++) {
		pref_min_C[i] = min(min_C[i], pref_min_C[i - 1]);
	}
	for (int h_val = 601; h_val >= 0; h_val--) {
		int min_C_idx = (h_val ? pref_min_C[h_val - 1].second : -1);
		for (int v = 0; v <= 2 * N; v++) {
			queries[v].clear();
		}
		for (int max_occ = 0; max_occ <= N; max_occ++) {
			for (int carry = 0; carry <= N; carry++) {
				if (h_val == 601) {
					dp[h_val][max_occ][carry] = (carry ? (ll)1e18 : 0);
					continue;
				}
				ll ret = (ll)1e18;
				int cur_amt = vec[h_val].size() + carry;
				if (cur_amt <= max_occ) {
					dp[h_val][max_occ][carry] = dp[h_val + 1][max_occ][0];
				} else if (min_C_idx == -1 || max_occ == 0) {
					for (int x : {0, 1}) {
						if (cur_amt - x > N) {
							continue;
						}
						ret = min(ret, dp[h_val + 1][x][cur_amt - x] - (ll)x * K);
					}
					dp[h_val][max_occ][carry] = ret + (ll)cur_amt * K;
				} else {
					int l = max(cur_amt - N, max_occ), r = min(N, cur_amt);
					for (int x = l; x <= r; x++) {
						ret = min(ret, dp[h_val + 1][x][cur_amt - x] + (ll)x * (C[min_C_idx] - K));
					}
					dp[h_val][max_occ][carry] = (ll)cur_amt * K - (ll)max_occ * C[min_C_idx];
					if (l <= r) {
						queries[cur_amt].eb(l, r, &dp[h_val][max_occ][carry]);
					}
				}
			}
		}
		if (h_val == 601 || min_C_idx == -1) {
			continue;
		}
		for (int v = 0; v <= 2 * N; v++) {
			arr[v].clear();
		}
		for (int max_occ = 0; max_occ <= N; max_occ++) {
			for (int carry = 0; carry <= N; carry++) {
				arr[max_occ + carry].pb(dp[h_val + 1][max_occ][carry] + (ll)max_occ * (C[min_C_idx] - K));
			}
		}
		for (int v = 0; v <= 2 * N; v++) {
			deque<int> Q;
			int idx = 0;
			for (auto [l, r, pos] : queries[v]) {
				while (idx <= r) {
					while (!Q.empty() && arr[v][Q.back()] >= arr[v][idx]) {
						Q.pop_back();
					}
					Q.pb(idx);
					idx++;
				}
				while (Q.front() < l) {
					Q.pop_front();
				}
				*pos += arr[v][Q.front()];
			}
		}
	}
	cout << dp[0][0][0] << '\n';
}

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