Submission #1216337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216337		trimkus	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	1065 ms	4396 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<array<int, 2>> a(n);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 2; ++j) {
			cin >> a[i][j];	
		}
		swap(a[i][0], a[i][1]);
	}
	sort(begin(a), end(a), [&](array<int, 2> x, array<int, 2> y) {
		if (x[0] == -1) return false;
		if (y[0] == -1) return true;
		if (x[0] == y[0]) {
			return x[1] < y[1];
		}
		return x[0] < y[0];
	});
	//~ for (int i = 0; i < n; ++i) {
		//~ cout << a[i][0] << " " << a[i][1] << "\n";
	//~ }
	ld res = 1e9 + 1;
	for (int i = 0; i <= n; ++i) {
		ld mult = 1, tim = 0;
		//~ vector<vector<double>> 
		bool bad = false;
		for (int j = 0; j < i; ++j) {
			if (a[j][0] == -1) {
				bad = true;
				break;
			}
			tim += 1.0 * a[j][0] / mult;
			mult += 1;
		}
		if (bad) {
			continue;
		}
		if (mult - 1 >= k) {
			res = min(res, tim);
			continue;
		}
		vector<vector<ld>> dp(n + 1, vector<ld>(k + 1, 1e9 + 1));
		dp[i][mult - 1] = tim;
		for (int j = i; j < n; ++j) {
			for (int t = 0; t <= k; ++t) {
				dp[j + 1][t] = min(dp[j + 1][t], dp[j][t]);
				if (t + 1 <= k) {
					dp[j + 1][t + 1] = min(dp[j + 1][t + 1],
						dp[j][t] + 1.0 * a[j][1] / mult);
				}
			}
		}
		//~ cout << i << " = " << dp[n][k] << "\n";
		res = min(res, dp[n][k]);
	}
	cout << fixed << setprecision(9) << res << "\n";
}

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