oj.uz

Submission #696094

# Submission time Handle Problem Language Result Execution time Memory
696094 2023-02-05T12:04:02 Z ethening Let's Win the Election (JOI22_ho_t3) C++17
21 / 100
 518 ms 3652 KB 
#include "bits/stdc++.h"
#include <functional>
#include <iomanip>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	vector<pii> pl(n + 5);
	for (int i = 1; i <= n; i++) {
		cin >> pl[i].first >> pl[i].second;
		if (pl[i].second == -1) pl[i].second = 1e9;
	}
	sort(pl.begin() + 1, pl.begin() + n + 1, [](pii& u, pii& v) {
		if (u.second == v.second) return u.first < v.first;
		else return u.second < v.second;
	});
	vector<vector<int>> suffix(n + 5, vector<int>(k + 5, 1e9));
	for (int i = n; i >= 1; i--) {
		for (int j = 0; j <= k; j++) {
			if (j > n - i + 1) break;
			if (i == n) {
				if (j == 0) suffix[i][j] = 0;
				else if (j == 1) suffix[i][j] = pl[i].first;
			}
			else {
				suffix[i][j] = suffix[i + 1][j];
				if (j > 0) suffix[i][j] = min(suffix[i][j], suffix[i + 1][j - 1] + pl[i].first);
			}
			// cout << "i: " << i << " j: " << j << " suf[i][j]: " << suffix[i][j] << endl;
		}
	}
	double ans = 1e16;
	for (int coop = 0; coop <= k; coop++) {
		// cout << "###" << coop << endl;
		vector<vector<double>> dp(n + 5, vector<double>(k + 5, 1e16));
		for (int i = 1; i <= k; i++) {
			for (int j = 0; j <= min(coop, i); j++) {
				if (i == 1) {
					if (j == 0) dp[i][j] = pl[i].first / (coop + 1.0);
					if (j > 0 && pl[i].second != -1) dp[i][j] = pl[i].second;
				}
				else {
					dp[i][j] = min(dp[i][j], dp[i - 1][j] + pl[i].first / (coop + 1.0));
					if (j > 0 && pl[i].second != -1) {
						dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + pl[i].second / (j - 1 + 1.0));
					}
				}
				// cout << i << " " << j << " " << dp[i][j] << endl;
				if (j == coop) {
					// cout << "@" << i << " " << j << " " << dp[i][j] << " $ " << k - i << " " << suffix[i + 1][k - i] << " " << dp[i][j] + suffix[i + 1][k - i] / (coop + 1.0) << "\n";
					if (i < k) {
						ans = min(ans, dp[i][j] + suffix[i + 1][k - i] / (coop + 1.0));
					}
					else {
						ans = min(ans, dp[i][j]);
					}
				}
			}
		}
	}
	cout << fixed << setprecision(9) << ans << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 4 ms 684 KB Output is correct
6 Correct 22 ms 1132 KB Output is correct
7 Correct 98 ms 2296 KB Output is correct
8 Correct 269 ms 2652 KB Output is correct
9 Correct 463 ms 3528 KB Output is correct
10 Correct 199 ms 2468 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 4 ms 684 KB Output is correct
6 Correct 22 ms 1132 KB Output is correct
7 Correct 98 ms 2296 KB Output is correct
8 Correct 269 ms 2652 KB Output is correct
9 Correct 463 ms 3528 KB Output is correct
10 Correct 199 ms 2468 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 30 ms 1368 KB Output is correct
13 Correct 30 ms 1280 KB Output is correct
14 Correct 31 ms 1280 KB Output is correct
15 Correct 225 ms 2748 KB Output is correct
16 Correct 211 ms 2768 KB Output is correct
17 Correct 197 ms 2764 KB Output is correct
18 Correct 468 ms 3524 KB Output is correct
19 Correct 456 ms 3588 KB Output is correct
20 Correct 518 ms 3496 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 3620 KB Output is correct
2 Correct 472 ms 3652 KB Output is correct
3 Correct 456 ms 3356 KB Output is correct
4 Correct 484 ms 3504 KB Output is correct
5 Correct 462 ms 3520 KB Output is correct
6 Correct 447 ms 3500 KB Output is correct
7 Correct 450 ms 3448 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 4 ms 684 KB Output is correct
6 Correct 22 ms 1132 KB Output is correct
7 Correct 98 ms 2296 KB Output is correct
8 Correct 269 ms 2652 KB Output is correct
9 Correct 463 ms 3528 KB Output is correct
10 Correct 199 ms 2468 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 30 ms 1368 KB Output is correct
13 Correct 30 ms 1280 KB Output is correct
14 Correct 31 ms 1280 KB Output is correct
15 Correct 225 ms 2748 KB Output is correct
16 Correct 211 ms 2768 KB Output is correct
17 Correct 197 ms 2764 KB Output is correct
18 Correct 468 ms 3524 KB Output is correct
19 Correct 456 ms 3588 KB Output is correct
20 Correct 518 ms 3496 KB Output is correct
21 Incorrect 1 ms 212 KB Output isn't correct
22 Halted 0 ms 0 KB -