Submission #1216352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216352		trimkus	Let's Win the Election (JOI22_ho_t3)	C++20	5 / 100	2592 ms	4400 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]);
	}
	//~ for (int i = 0; i < n; ++i) {
		//~ cout << a[i][0] << " " << a[i][1] << "\n";
	//~ }
	//~ cerr << "\n";
	ld res = 1e9 + 1;
	for (int add = 0; add < 2; ++add) {
		for (int i = 0; i <= n; ++i) {
			ld mult = 1, tim = 0;
			//~ vector<vector<double>> 
			bool bad = false;
			vector<array<int, 2>> na = a;
			for (int j = 0; j < i; ++j) {
				if (j + add < i) {
					sort(rbegin(na), rend(na), [&](array<int, 2> x, array<int, 2> y) {
						if (x[0] == -1) return false;
						if (y[0] == -1) return true;
						return x[0] < y[0];
					});
				} else {
					sort(rbegin(na), rend(na), [&](array<int, 2> x, array<int, 2> y) {
						if (x[0] == -1) return false;
						if (y[0] == -1) return true;
						return x[0] * (mult + 1) + y[1] * mult < y[0] * (mult + 1) + x[1] * mult;
					});
				}
				auto now = na.back();
				na.pop_back();
				if (now[0] == -1) {
					bad = true;
					break;
				}
				//~ cerr << now[1] << " " << now[0] << "\n";
				tim += 1.0 * now[0] / mult;
				mult += 1;
			}
			//~ cerr << "Done picked!\n";
			if (bad) {
				//~ cerr << "bad!\n";
				continue;
			}
			if (mult - 1 >= k) {
				//~ cout << i << " = " << tim << "\n";
				res = min(res, tim);
				continue;
			}
			vector<vector<ld>> dp(n + 1, vector<ld>(k + 1, 1e9 + 1));
			dp[i][mult - 1] = tim;
			reverse(begin(na), end(na));
			for (int j = i; j < n; ++j) {
				//~ cerr << na[j - i][1] << " " << na[j - i][0] << "\n";
				for (int t = 0; t <= k; ++t) {
					dp[j + 1][t] = min(dp[j + 1][t], dp[j][t]);
					if (t + 1 <= k) {
						//~ cerr << dp[j][t] << " + " << 1.0 * na[j - i][1] / mult << "\n";
						dp[j + 1][t + 1] = min(dp[j + 1][t + 1],
							dp[j][t] + 1.0 * na[j - i][1] / mult);
					}
				}
			}
			//~ cout << i << " = " << dp[n][k] << "\n";
			res = min(res, dp[n][k]);
		}
	}
	cout << fixed << setprecision(3) << res << "\n";
}

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