Submission #1038186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038186		AmirAli_H1	Ski 2 (JOI24_ski2)	C++17	86 / 100	120 ms	4952 KiB

Main

// In the name of Allah

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

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n; ll k;
const int maxn = 600 + 4;
const ll oo = 1e18 + 4;
pll A[maxn]; ll ans = oo, res = 0;
ll dp[2][maxn][maxn], mn[maxn], cnt[maxn];

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> A[i].F >> A[i].S;
	
	sort(A, A + n);
	ll x = A[0].F; A[0].F -= x;
	for (int i = 1; i < n; i++) {
		if (A[i].F == x) {
			A[i].F++; res += k;
		}
		A[i].F -= x;
	}
	sort(A, A + n);
	
	fill(mn, mn + maxn, oo);
	for (int i = 0; i < n; i++) {
		mn[A[i].F] = min(mn[A[i].F], A[i].S);
		cnt[A[i].F]++;
	}
	for (int i = 1; i < maxn; i++) mn[i] = min(mn[i], mn[i - 1]);
	
	for (int i = 0; i < maxn; i++) {
		if (i == 0) {
			for (int j1 = 0; j1 <= n; j1++) {
				for (int j2 = 0; j2 <= n; j2++) {
					dp[i & 1][j1][j2] = oo;
					if (j1 == 1 && j2 == 0) dp[i & 1][j1][j2] = 0;
				}
			}
		}
		else {
			for (int j1 = 0; j1 <= n; j1++) {
				for (int j2 = 1; j2 <= n; j2++) {
					dp[i & 1][j1 + 1][j2 - 1] = min(dp[i & 1][j1 + 1][j2 - 1], dp[i & 1][j1][j2] + mn[i - 1]);
				}
			}
		}
		if (i + 1 >= maxn) continue;
		
		for (int j1 = 0; j1 <= n; j1++) {
			for (int j2 = 0; j2 <= n; j2++) {
				dp[(i + 1) & 1][j1][j2] = oo;
			}
		}
		for (int j1 = 0; j1 <= n; j1++) {
			for (int j2 = 0; j2 <= n; j2++) {
				if (dp[i & 1][j1][j2] == oo) continue;
				ll x = dp[i & 1][j1][j2] + (k * j2);
				int r1 = j1, r2 = j2 + cnt[i + 1];
				int e = min(r1, r2); r2 -= e;
				dp[(i + 1) & 1][r1][r2] = min(dp[(i + 1) & 1][r1][r2], x);
			}
		}
	}
	
	for (int j1 = 0; j1 <= n; j1++) ans = min(ans, dp[(maxn - 1) & 1][j1][0]);
	ans += res;
	
	cout << ans << endl;
	
	return 0;
}

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