Submission #1137111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137111		NK_	Ski 2 (JOI24_ski2)	C++20	100 / 100	191 ms	2632 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define f first
#define s second
#define mp make_pair

using ll = long long;
template<class T> using V = vector<T>;
template<class T, size_t SZ> using AR = array<T, SZ>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = V<int>;
using vl = V<ll>;
using vpi = V<pi>;
using vpl = V<pl>;

const ll INF = 1e18;
const ll hax = 1e9 + 2008;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; ll K; cin >> N >> K;

	vpl A(N); for(int i = 0; i < N; i++) cin >> A[i].f >> A[i].s;

	sort(begin(A), end(A));

	vpl mn; 
	{
		for(int i = 0; i < N; i++) mn.pb(A[i]);
		sort(begin(mn), end(mn));

		vpl a = {mp(-1, INF)};
		for(int i = 0; i < N; i++) {
			if (a.back().s > mn[i].s) a.pb(mn[i]);
		}

		mn = a;

		// for(auto& x : mn) cout << x.f << " " << x.s << endl;
	}

	vl H; for(auto& x : A) { 
		for(int d = 0; d <= 2; d++) H.pb(x.f + d);
	}

	sort(begin(H), end(H)); H.erase(unique(begin(H), end(H)), end(H));
	int M = sz(H); H.pb(hax);
	
	auto get = [&](ll x) {
		return (*prev(upper_bound(begin(mn), end(mn), mp(x, -1LL)))).s;
	};

	auto cmin = [&](ll &a, ll b) { a = min(a, b); };

	auto sum = [&](ll n) { return (n * 1LL * (n - 1)) / 2LL; };


	V<vl> dp(N + 1, vl(N + 1, INF)), ndp; // dp[height][leaves][have]	
	dp[1][0] = 0;

	for(int i = 0, j = 0; i < M; i++) {
		ndp = V<vl>(N + 1, vl(N + 1, INF));

		int amt = 0; ll dif = H[i + 1] - H[i];
		while(j < N && A[j].f == H[i]) amt++, j++;

		ll cost = get(H[i]); // make new leaf
		// cout << H[i] << " => " << amt << " | " << cost << endl;

		// add the new ones
		for(int l = 1; l <= min(N, j + 1); l++) for(int x = 0; x <= min(N, j + 1); x++) if (dp[l][x] != INF) {
			if (x + amt <= N) cmin(ndp[l][x + amt], dp[l][x]);
		}

		for(int l = 1; l <= min(N, j + 1); l++) for(int x = 0; x <= min(N, j + 1); x++) if (ndp[l][x] != INF) {
			ll can = min(x + 0LL, dif * 1LL * l);
			ll ex = l * 1LL * sum(can / l) + (can % l) * 1LL * (can / l);

			// cout << l << " " << x << " -> " << can << " ===> " << ndp[l][x] << " " << ex << endl;

			cmin(ndp[l][x - can], ndp[l][x] + ex * K);
		}
		// cout << i << " " << H[i] << endl;

		for(int l = 1; l <= min(N, j + 1); l++) for(int x = 0; x <= min(N, j + 1); x++) if (ndp[l][x] != INF) {	
			if (l + 1 <= N && x) cmin(ndp[l + 1][x - 1], ndp[l][x] + cost);
			// cout << l << " " << x << " => " << ndp[l][x] << endl;
			ndp[l][x] += x * 1LL * dif * K;
		}

		dp.swap(ndp);
	}

	ll ans = INF;
	for(int l = 1; l <= N; l++) cmin(ans, dp[l][0]);

	cout << ans << nl;



	exit(0-0);
}

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