Submission #526598

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526598	2022-02-15T13:59:38 Z	hmm789	Let's Win the Election (JOI22_ho_t3)	C++14	10 / 100	706 ms	984680 KB

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;
	pair<int, int> a[n];
	for(int i = 0; i < n; i++) {
		cin >> a[i].second >> a[i].first;
		if(a[i].first == -1) a[i].first = 1e9;
	}
	sort(a, a+n);
	double dp[n+1][k+1][k+1]; 
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= k; j++) {
			for(int m = 0; m <= k; m++) {
				if(m == 0 && i == 0 && j == 0) dp[i][j][m] = 0;
				else if(i == 0 || i < m || i < j || m < j) dp[i][j][m] = 1e9;
				else if(m == 0) dp[i][j][m] = 0;
				else if(j == 0) dp[i][j][m] = min(dp[i-1][j][m-1] + a[i-1].second*1.0/(j+1), dp[i-1][j][m]);
				else dp[i][j][m] = min(dp[i-1][j][m-1] + a[i-1].second*1.0/(j+1), min(dp[i-1][j-1][m-1] + a[i-1].first*1.0/j, dp[i-1][j][m]));
			}
		}
	}
	double res = 1e9;
	for(int i = 0; i <= k; i++) res = min(res, dp[n][i][k]);
	cout << fixed << setprecision(5) << res;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	10 ms	10508 KB	Output is correct
6	Correct	60 ms	62564 KB	Output is correct
7	Correct	180 ms	247364 KB	Output is correct
8	Correct	434 ms	554672 KB	Output is correct
9	Correct	594 ms	984680 KB	Output is correct
10	Correct	299 ms	483448 KB	Output is correct

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	10 ms	10508 KB	Output is correct
6	Correct	60 ms	62564 KB	Output is correct
7	Correct	180 ms	247364 KB	Output is correct
8	Correct	434 ms	554672 KB	Output is correct
9	Correct	594 ms	984680 KB	Output is correct
10	Correct	299 ms	483448 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	67 ms	89676 KB	Output is correct
13	Correct	72 ms	89708 KB	Output is correct
14	Correct	85 ms	89672 KB	Output is correct
15	Correct	310 ms	483352 KB	Output is correct
16	Correct	323 ms	483376 KB	Output is correct
17	Correct	329 ms	483416 KB	Output is correct
18	Correct	617 ms	984544 KB	Output is correct
19	Correct	577 ms	984644 KB	Output is correct
20	Correct	592 ms	984648 KB	Output is correct

Subtask #3

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	208 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Incorrect	1 ms	208 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #4

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	208 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Incorrect	1 ms	208 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #5

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	0 ms	208 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Incorrect	1 ms	208 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #6

0 / 11.0

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

Subtask #7

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	10 ms	10508 KB	Output is correct
6	Correct	60 ms	62564 KB	Output is correct
7	Correct	180 ms	247364 KB	Output is correct
8	Correct	434 ms	554672 KB	Output is correct
9	Correct	594 ms	984680 KB	Output is correct
10	Correct	299 ms	483448 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	67 ms	89676 KB	Output is correct
13	Correct	72 ms	89708 KB	Output is correct
14	Correct	85 ms	89672 KB	Output is correct
15	Correct	310 ms	483352 KB	Output is correct
16	Correct	323 ms	483376 KB	Output is correct
17	Correct	329 ms	483416 KB	Output is correct
18	Correct	617 ms	984544 KB	Output is correct
19	Correct	577 ms	984644 KB	Output is correct
20	Correct	592 ms	984648 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Correct	1 ms	204 KB	Output is correct
24	Correct	0 ms	204 KB	Output is correct
25	Correct	0 ms	208 KB	Output is correct
26	Correct	1 ms	204 KB	Output is correct
27	Correct	0 ms	204 KB	Output is correct
28	Correct	1 ms	204 KB	Output is correct
29	Incorrect	1 ms	208 KB	Output isn't correct
30	Halted	0 ms	0 KB	-