Submission #1209248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209248		duckindog	Ski 2 (JOI24_ski2)	C++17	100 / 100	251 ms	466932 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 300 + 10,
			MAX = 1'000'000'000'000'000'000;
int n, k;
int h[N], c[N];

int minC[N * 2], cnt[N * 2];
int f[N * 2][N][N];

inline void getMin(auto& x, const auto& y) { x = min(x, y); }

int32_t main() { 
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> k;
	for (int i = 1; i <= n; ++i) cin >> h[i] >> c[i];

	vector<int> allH;
	for (int i = 1; i <= n; ++i) allH.push_back(h[i]), allH.push_back(h[i] + 1);
	{ // discrete
		sort(allH.begin(), allH.end());
		allH.erase(unique(allH.begin(), allH.end()), allH.end());
	}
	const int sz = allH.size();

	fill(minC, minC + sz + 1, MAX);
	for (int i = 1; i <= n; ++i) { 
		int itH = lower_bound(allH.begin(), allH.end(), h[i]) - allH.begin();
		getMin(minC[itH], c[i]);
		cnt[itH] += 1;
	}

	auto cal = [&](int m, int w, int num) { 
		int k = min(num / m, w);
    	return k * (k - 1) / 2 * m + k * (num - k * m);
	};

	memset(f, 14, sizeof f);
	f[0][1][0] = 0;

	int mn = MAX;
	for (int i = 0; i < sz; ++i) { 
		int w = (i == sz - 1 ? n : allH[i + 1] - allH[i]);
		for (int j = 1; j <= n; ++j) { 
			for (int t = 0; t <= n; ++t) { 
				int cur = f[i][j][t];
				if (cur >= MAX) continue;
				
				if (j < n) getMin(f[i][j + 1][t], cur + mn);
				int num = t + cnt[i];
				getMin(f[i + 1][j][max(0ll, num - j * w)], cur + 1ll * k * cal(j, w, num));
			}
		}
		mn = min(mn, minC[i]);
	}

	int answer = MAX;
	for (int i = 1; i <= n; ++i) getMin(answer, f[sz][i][0]);
	
	cout << answer << "\n";
}

Compilation message (stderr)

Main.cpp:15:20: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   15 | inline void getMin(auto& x, const auto& y) { x = min(x, y); }
      |                    ^~~~
Main.cpp:15:35: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   15 | inline void getMin(auto& x, const auto& y) { x = min(x, y); }
      |                                   ^~~~

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