Submission #526353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526353	2022-02-14T13:12:45 Z	model_code	Let's Win the Election (JOI22_ho_t3)	C++17	11 / 100	11 ms	460 KB

Main

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;

int N, K;
int A[509], B[509];
bool used[509];
double Answer = 1e9;

void dfs(int pos, int corp, double ti) {
	if (pos == K) {
		Answer = min(Answer, ti);
		return;
	}
	
	for (int i = 1; i <= N; i++) {
		if (used[i] == true) continue;
		used[i] = true;
		dfs(pos + 1, corp + 0, ti + 1.0 * A[i] / (corp + 1));
		if (B[i] != -1) {
			dfs(pos + 1, corp + 1, ti + 1.0 * B[i] / (corp + 1));
		}
		used[i] = false;
	}
}

int main() {
	// Step #1. Input
	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> A[i] >> B[i];
	assert(N <= 7);
	
	// Step #2. Brute Force
	dfs(0, 0, 0.0);
	
	// Step #3. Output
	printf("%.12lf\n", Answer);
	return 0;
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Runtime error	1 ms	332 KB	Execution killed with signal 6
6	Halted	0 ms	0 KB	-

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Runtime error	1 ms	332 KB	Execution killed with signal 6
6	Halted	0 ms	0 KB	-

Subtask #3

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	3 ms	204 KB	Output is correct
7	Correct	11 ms	292 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	8 ms	204 KB	Output is correct

Subtask #4

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	3 ms	204 KB	Output is correct
7	Correct	11 ms	292 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	8 ms	204 KB	Output is correct
16	Runtime error	1 ms	460 KB	Execution killed with signal 6
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	3 ms	204 KB	Output is correct
7	Correct	11 ms	292 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	8 ms	204 KB	Output is correct
16	Runtime error	1 ms	460 KB	Execution killed with signal 6
17	Halted	0 ms	0 KB	-

Subtask #6

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	1 ms	332 KB	Execution killed with signal 6
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	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Runtime error	1 ms	332 KB	Execution killed with signal 6
6	Halted	0 ms	0 KB	-