Submission #766609

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
766609	2023-06-26T01:23:37 Z	NK_	Let's Win the Election (JOI22_ho_t3)	C++17	10 / 100	9 ms	340 KB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

template<class T> using V = vector<T>;

const double eps = 1e-9;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	cout << fixed << setprecision(15);

	int N, K; cin >> N >> K;
	V<int> A(N), B(N); 
	for(int i = 0; i < N; i++) {
		cin >> A[i] >> B[i]; 
		if (B[i] == -1) B[i] = int(1e9);
	}

	double ans = double(1e9);

	for(int c = 0; c <= N; c++) {
		V<int> BI(N); iota(begin(BI), end(BI), 0);
		
		sort(begin(BI), end(BI), [&](int i, int j) {
			return B[i] < B[j];
		});


		V<int> AI; for(int i = c; i < N; i++) AI.push_back(BI[i]);

		sort(begin(AI), end(AI), [&](int i, int j) {
			return A[i] < A[j];
		});

		V<int> ord; 

		double res = 0;
		for(int i = 0; i < c; i++) {
			// cout << BI[i] << " " << B[BI[i]] << endl;
			res += double(B[BI[i]]) / double(i + 1);
		}
		for(int i = 0; i < K - c; i++) {
			// cout << AI[i] << " " << A[AI[i]] << endl;
			res += double(A[AI[i]]) / double(c + 1);
		}

		// cout << c << " " << res << endl;

		if (res+eps < ans) ans = res;
	}
	cout << ans << nl;


    return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	7 ms	320 KB	Output is correct
6	Correct	7 ms	212 KB	Output is correct
7	Correct	7 ms	324 KB	Output is correct
8	Correct	8 ms	340 KB	Output is correct
9	Correct	7 ms	320 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct

Subtask #2

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	7 ms	320 KB	Output is correct
6	Correct	7 ms	212 KB	Output is correct
7	Correct	7 ms	324 KB	Output is correct
8	Correct	8 ms	340 KB	Output is correct
9	Correct	7 ms	320 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	6 ms	316 KB	Output is correct
13	Correct	7 ms	212 KB	Output is correct
14	Correct	7 ms	224 KB	Output is correct
15	Correct	6 ms	212 KB	Output is correct
16	Correct	7 ms	336 KB	Output is correct
17	Correct	7 ms	340 KB	Output is correct
18	Correct	6 ms	340 KB	Output is correct
19	Correct	7 ms	212 KB	Output is correct
20	Correct	7 ms	316 KB	Output is correct

Subtask #3

0 / 11.0

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

Subtask #4

0 / 12.0

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

Subtask #5

0 / 33.0

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

Subtask #6

0 / 11.0

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

Subtask #7

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	316 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	7 ms	320 KB	Output is correct
6	Correct	7 ms	212 KB	Output is correct
7	Correct	7 ms	324 KB	Output is correct
8	Correct	8 ms	340 KB	Output is correct
9	Correct	7 ms	320 KB	Output is correct
10	Correct	3 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	6 ms	316 KB	Output is correct
13	Correct	7 ms	212 KB	Output is correct
14	Correct	7 ms	224 KB	Output is correct
15	Correct	6 ms	212 KB	Output is correct
16	Correct	7 ms	336 KB	Output is correct
17	Correct	7 ms	340 KB	Output is correct
18	Correct	6 ms	340 KB	Output is correct
19	Correct	7 ms	212 KB	Output is correct
20	Correct	7 ms	316 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	1 ms	212 KB	Output is correct
26	Correct	1 ms	320 KB	Output is correct
27	Correct	1 ms	316 KB	Output is correct
28	Correct	0 ms	316 KB	Output is correct
29	Incorrect	1 ms	212 KB	Output isn't correct
30	Halted	0 ms	0 KB	-