Submission #529595

#	Time	Username	Problem	Language	Result	Execution time	Memory
529595		fhvirus	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	395 ms	2344 KiB

Main

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

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, K; cin >> N >> K;
	vector< pair<int, int> > states(N);
	for (int i = 0; i < N; ++i) {
		cin >> states[i].second >> states[i].first;
		if (states[i].first == -1)
			states[i].first = 1'000'000'000;
	}
	sort(begin(states), end(states));

	double ans = 1e18;
	for (int g = 0; g <= K; ++g) {
		vector< vector<double> > dp(N + 1, vector<double>(K - g + 1, 1e18));
		dp[0][0] = 0;
		for (int i = 0; i < N; ++i)
			for (int j = 0; j <= K - g; ++j) {
				if (j < K - g)
					dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + (double) states[i].second / (g + 1));
				dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + (i - j < g ? (double) states[i].first / (i - j + 1) : .0));
			}
		ans = min(ans, dp[N][K - g]);
	}

	cout << setprecision(9) << fixed << ans << '\n';
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23