제출 #1216348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216348		trimkus	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	1396 ms	4404 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 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 + 1 < 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;
		}
		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;
		reverse(begin(na), end(na));
		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 * 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: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23