Submission #985564

#	Time	Username	Problem	Language	Result	Execution time	Memory
985564		maomao90	Ski 2 (JOI24_ski2)	C++17	100 / 100	343 ms	437904 KiB

Main

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <numeric>
#include <bitset>
#include <map>
#include <queue>
#include <cassert>
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<ll, ll, ll> lll;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const ll LINF = 1000000000000000005ll;
const int INF = 1000000005;
const int MAXN = 305;

int n, k;
ii hc[MAXN];
int vh[MAXN];
int mnc[MAXN];
ll dp[MAXN][MAXN][MAXN], pmnl[MAXN][MAXN][MAXN];
ll base[MAXN];
ll ans;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	REP (i, 1, n + 1) {
		cin >> hc[i].FI >> hc[i].SE;
	}
	if (n == 1) {
		cout << 0 << "\n";
		return 0;
	}
	sort(hc + 1, hc + n + 1);
	//vh.pb(-1);
	int lst = 0;
	REP (i, 1, n + 1) {
		mxto(lst, hc[i].FI);
		vh[i] = lst++;
		cerr << vh[i] << " ";
		//vh.pb(lst++);
	}
	cerr << "\n";
	//assert(SZ(vh) == n);
	//sort(ALL(vh));
	//vh.erase(unique(ALL(vh)), vh.end());
	mnc[0] = INF;
	REP (i, 1, n + 1) {
		mnc[i] = INF;
		REP (j, 1, n + 1) {
			if (hc[j].FI > vh[i]) {
				break;
			}
			mnto(mnc[i], hc[j].SE);
		}
		cerr << i << ": " << mnc[i] << "\n";
	}
	REP (h, 0, n + 1) {
		REP (i, 0, n + 1) {
			REP (l, 0, n + 1) {
				dp[h][i][l] = LINF;
			}
		}
	}
	ll tmp = 0;
	REP (i, 2, n + 1) {
		tmp += (hc[i].FI == hc[1].FI) * k;
	}
	dp[1][1][1] = tmp;
	REP (i, 1, n + 1) {
		pmnl[1][i][0] = LINF;
		REP (l, 1, n + 1) {
			pmnl[1][i][l] = min(pmnl[1][i][l - 1], dp[1][i][l] - (ll) l * mnc[1]);
		}
	}
	ans = LINF;
	REP (h, 2, n + 1) {
		REP (i, 1, n + 1) {
			if (hc[i].FI > vh[h]) {
				break;
			}
			base[i] = 0;
			REP (j, i + 1, n + 1) {
				base[i] += (hc[j].FI <= vh[h]) * k;
			}
		}
		REP (l, 1, n) {
			deque<int> dq;
			auto add = [&] (int i) {
				while (!dq.empty() && dp[h - 1][dq.back()][l] >= dp[h - 1][i][l]) {
					dq.pop_back();
				}
				dq.pb(i);
			};
			REP (i, 1, l + 1) {
				add(i);
			}
			REP (i, l + 1, n + 1) {
				if (hc[i].FI > vh[h]) {
					break;
				}
				while (!dq.empty() && dq.front() < i - l) {
					dq.pop_front();
				}
				add(i);
				mnto(dp[h][i][l], dp[h - 1][dq.front()][l] + base[i]);
				/*
				REP (j, i - l, i + 1) {
					mnto(dp[h][i][l], dp[h - 1][j][l] + base[i]);
				}
				*/
			}
		}
		REP (i, 1, n + 1) {
			if (hc[i].FI > vh[h]) {
				break;
			}
			REP (l, 1, i) {
				mnto(dp[h][i][l], pmnl[h - 1][i - l][l - 1] + (ll) l * mnc[h - 1] + base[i]);
				/*
				REP (j, 1, l) {
					mnto(dp[h][i][l], dp[h - 1][i - l][j] + (ll) (l - j) * mnc[h - 1] + base[i]);
				}
				*/
				cerr << h << " " << i << " " << l << ": " << dp[h][i][l] << "\n";
			}
		}
		REP (i, 1, n + 1) {
			pmnl[h][i][0] = LINF;
			REP (l, 1, n + 1) {
				pmnl[h][i][l] = min(pmnl[h][i][l - 1], dp[h][i][l] - (ll) l * mnc[h]);
			}
		}
	}
	REP (h, 1, n + 1) {
		REP (l, 1, n) {
			mnto(ans, dp[h][n][l]);
		}
	}
	cout << ans << "\n";
	return 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