Submission #1115452

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1115452	2024-11-20T13:12:28 Z	vjudge1	Bootfall (IZhO17_bootfall)	C++17	13 / 100	1000 ms	49744 KB

bootfall

#include "bits/stdc++.h"

using namespace std;

int vis[500][25001];
int poss[25001];
int mark[501];
int sm[25001];
int a[500];
int N;

void dfs(int skip, int u = -1, int d = 0) {
	if (-1 == u || skip != vis[u][d]) {
		if (-1 ^ u) {
			vis[u][d] = skip;
		}
		sm[d] = 1;
		for (int j = u + 1; j < N; j ++) {
			if (j ^ skip) {
				dfs(skip, j, d + a[j]);
			}
		}
	}
}

void solve() {
	cin >> N;

	for (int i = 0; i < N; i ++) {
		cin >> a[i];
	}

	memset(vis, 0x3f, sizeof(vis));
	int f = 1;
	for (int i = 0; i <= N; i ++) {
		memset(sm, 0, sizeof(sm));
		int sum = 0;
		for (int j = 0; j < N; j ++) {
			if (i ^ j) {
				sum += a[j];
			}
		}
		dfs(i);
		if (N == i) {
			f = sm[sum / 2] && !(sum & 1);
			continue;
		}
		for (int j = 0; j < 25001; j ++) {
			if (sm[j] && j * 2 > sum ) {
				poss[j * 2 - sum] ++;
			}
		}
	}
	if (0 == f) {
		cout << 0 << endl;
		return;
	}
	vector<int> ans;
	for (int j = 1; j < 25001; j ++) {
		if (poss[j] == N) {
			ans.push_back(j);
		}
	}
	cout << ans.size() << endl;
	for (int i : ans) {
		cout << i << ' ';
	}
	cout << endl;
}

int main() {
	solve();
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	49488 KB	Output is correct
2	Correct	8 ms	49488 KB	Output is correct
3	Correct	11 ms	49256 KB	Output is correct
4	Correct	13 ms	49656 KB	Output is correct
5	Correct	18 ms	49488 KB	Output is correct
6	Correct	17 ms	49500 KB	Output is correct
7	Correct	19 ms	49488 KB	Output is correct
8	Correct	17 ms	49504 KB	Output is correct
9	Correct	18 ms	49488 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	49488 KB	Output is correct
2	Correct	8 ms	49488 KB	Output is correct
3	Correct	11 ms	49256 KB	Output is correct
4	Correct	13 ms	49656 KB	Output is correct
5	Correct	18 ms	49488 KB	Output is correct
6	Correct	17 ms	49500 KB	Output is correct
7	Correct	19 ms	49488 KB	Output is correct
8	Correct	17 ms	49504 KB	Output is correct
9	Correct	18 ms	49488 KB	Output is correct
10	Correct	11 ms	49488 KB	Output is correct
11	Correct	13 ms	49488 KB	Output is correct
12	Correct	23 ms	49488 KB	Output is correct
13	Correct	24 ms	49312 KB	Output is correct
14	Correct	26 ms	49492 KB	Output is correct
15	Correct	19 ms	49504 KB	Output is correct
16	Correct	19 ms	49488 KB	Output is correct
17	Correct	22 ms	49232 KB	Output is correct
18	Correct	19 ms	49504 KB	Output is correct
19	Correct	22 ms	49488 KB	Output is correct
20	Correct	17 ms	49308 KB	Output is correct

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	49488 KB	Output is correct
2	Correct	8 ms	49488 KB	Output is correct
3	Correct	11 ms	49256 KB	Output is correct
4	Correct	13 ms	49656 KB	Output is correct
5	Correct	18 ms	49488 KB	Output is correct
6	Correct	17 ms	49500 KB	Output is correct
7	Correct	19 ms	49488 KB	Output is correct
8	Correct	17 ms	49504 KB	Output is correct
9	Correct	18 ms	49488 KB	Output is correct
10	Correct	11 ms	49488 KB	Output is correct
11	Correct	13 ms	49488 KB	Output is correct
12	Correct	23 ms	49488 KB	Output is correct
13	Correct	24 ms	49312 KB	Output is correct
14	Correct	26 ms	49492 KB	Output is correct
15	Correct	19 ms	49504 KB	Output is correct
16	Correct	19 ms	49488 KB	Output is correct
17	Correct	22 ms	49232 KB	Output is correct
18	Correct	19 ms	49504 KB	Output is correct
19	Correct	22 ms	49488 KB	Output is correct
20	Correct	17 ms	49308 KB	Output is correct
21	Correct	371 ms	49744 KB	Output is correct
22	Correct	733 ms	49488 KB	Output is correct
23	Correct	135 ms	49480 KB	Output is correct
24	Execution timed out	1066 ms	49480 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #4
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	49488 KB	Output is correct
2	Correct	8 ms	49488 KB	Output is correct
3	Correct	11 ms	49256 KB	Output is correct
4	Correct	13 ms	49656 KB	Output is correct
5	Correct	18 ms	49488 KB	Output is correct
6	Correct	17 ms	49500 KB	Output is correct
7	Correct	19 ms	49488 KB	Output is correct
8	Correct	17 ms	49504 KB	Output is correct
9	Correct	18 ms	49488 KB	Output is correct
10	Correct	11 ms	49488 KB	Output is correct
11	Correct	13 ms	49488 KB	Output is correct
12	Correct	23 ms	49488 KB	Output is correct
13	Correct	24 ms	49312 KB	Output is correct
14	Correct	26 ms	49492 KB	Output is correct
15	Correct	19 ms	49504 KB	Output is correct
16	Correct	19 ms	49488 KB	Output is correct
17	Correct	22 ms	49232 KB	Output is correct
18	Correct	19 ms	49504 KB	Output is correct
19	Correct	22 ms	49488 KB	Output is correct
20	Correct	17 ms	49308 KB	Output is correct
21	Correct	371 ms	49744 KB	Output is correct
22	Correct	733 ms	49488 KB	Output is correct
23	Correct	135 ms	49480 KB	Output is correct
24	Execution timed out	1066 ms	49480 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	49488 KB	Output is correct
2	Correct	8 ms	49488 KB	Output is correct
3	Correct	11 ms	49256 KB	Output is correct
4	Correct	13 ms	49656 KB	Output is correct
5	Correct	18 ms	49488 KB	Output is correct
6	Correct	17 ms	49500 KB	Output is correct
7	Correct	19 ms	49488 KB	Output is correct
8	Correct	17 ms	49504 KB	Output is correct
9	Correct	18 ms	49488 KB	Output is correct
10	Correct	11 ms	49488 KB	Output is correct
11	Correct	13 ms	49488 KB	Output is correct
12	Correct	23 ms	49488 KB	Output is correct
13	Correct	24 ms	49312 KB	Output is correct
14	Correct	26 ms	49492 KB	Output is correct
15	Correct	19 ms	49504 KB	Output is correct
16	Correct	19 ms	49488 KB	Output is correct
17	Correct	22 ms	49232 KB	Output is correct
18	Correct	19 ms	49504 KB	Output is correct
19	Correct	22 ms	49488 KB	Output is correct
20	Correct	17 ms	49308 KB	Output is correct
21	Correct	371 ms	49744 KB	Output is correct
22	Correct	733 ms	49488 KB	Output is correct
23	Correct	135 ms	49480 KB	Output is correct
24	Execution timed out	1066 ms	49480 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	49488 KB	Output is correct
2	Correct	8 ms	49488 KB	Output is correct
3	Correct	11 ms	49256 KB	Output is correct
4	Correct	13 ms	49656 KB	Output is correct
5	Correct	18 ms	49488 KB	Output is correct
6	Correct	17 ms	49500 KB	Output is correct
7	Correct	19 ms	49488 KB	Output is correct
8	Correct	17 ms	49504 KB	Output is correct
9	Correct	18 ms	49488 KB	Output is correct
10	Correct	11 ms	49488 KB	Output is correct
11	Correct	13 ms	49488 KB	Output is correct
12	Correct	23 ms	49488 KB	Output is correct
13	Correct	24 ms	49312 KB	Output is correct
14	Correct	26 ms	49492 KB	Output is correct
15	Correct	19 ms	49504 KB	Output is correct
16	Correct	19 ms	49488 KB	Output is correct
17	Correct	22 ms	49232 KB	Output is correct
18	Correct	19 ms	49504 KB	Output is correct
19	Correct	22 ms	49488 KB	Output is correct
20	Correct	17 ms	49308 KB	Output is correct
21	Correct	371 ms	49744 KB	Output is correct
22	Correct	733 ms	49488 KB	Output is correct
23	Correct	135 ms	49480 KB	Output is correct
24	Execution timed out	1066 ms	49480 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Submission #1115452

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 7.0 / 7.0

Subtask #3 0 / 15.0

Subtask #4 0 / 16.0

Subtask #5 0 / 21.0

Subtask #6 0 / 35.0

Subtask #1
6.0 / 6.0

Subtask #2
7.0 / 7.0

Subtask #3
0 / 15.0

Subtask #4
0 / 16.0

Subtask #5
0 / 21.0

Subtask #6
0 / 35.0