Submission #1115450

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1115450	2024-11-20T13:11:45 Z	vjudge1	Bootfall (IZhO17_bootfall)	C++17	13 / 100	362 ms	49660 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 < 2501; 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 < 2501; 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	49660 KB	Output is correct
3	Correct	8 ms	49488 KB	Output is correct
4	Correct	7 ms	49488 KB	Output is correct
5	Correct	8 ms	49660 KB	Output is correct
6	Correct	8 ms	49488 KB	Output is correct
7	Correct	9 ms	49488 KB	Output is correct
8	Correct	9 ms	49488 KB	Output is correct
9	Correct	8 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	49660 KB	Output is correct
3	Correct	8 ms	49488 KB	Output is correct
4	Correct	7 ms	49488 KB	Output is correct
5	Correct	8 ms	49660 KB	Output is correct
6	Correct	8 ms	49488 KB	Output is correct
7	Correct	9 ms	49488 KB	Output is correct
8	Correct	9 ms	49488 KB	Output is correct
9	Correct	8 ms	49488 KB	Output is correct
10	Correct	8 ms	49488 KB	Output is correct
11	Correct	13 ms	49656 KB	Output is correct
12	Correct	13 ms	49488 KB	Output is correct
13	Correct	16 ms	49488 KB	Output is correct
14	Correct	15 ms	49500 KB	Output is correct
15	Correct	12 ms	49488 KB	Output is correct
16	Correct	12 ms	49488 KB	Output is correct
17	Correct	12 ms	49488 KB	Output is correct
18	Correct	15 ms	49488 KB	Output is correct
19	Correct	10 ms	49488 KB	Output is correct
20	Correct	8 ms	49488 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	49660 KB	Output is correct
3	Correct	8 ms	49488 KB	Output is correct
4	Correct	7 ms	49488 KB	Output is correct
5	Correct	8 ms	49660 KB	Output is correct
6	Correct	8 ms	49488 KB	Output is correct
7	Correct	9 ms	49488 KB	Output is correct
8	Correct	9 ms	49488 KB	Output is correct
9	Correct	8 ms	49488 KB	Output is correct
10	Correct	8 ms	49488 KB	Output is correct
11	Correct	13 ms	49656 KB	Output is correct
12	Correct	13 ms	49488 KB	Output is correct
13	Correct	16 ms	49488 KB	Output is correct
14	Correct	15 ms	49500 KB	Output is correct
15	Correct	12 ms	49488 KB	Output is correct
16	Correct	12 ms	49488 KB	Output is correct
17	Correct	12 ms	49488 KB	Output is correct
18	Correct	15 ms	49488 KB	Output is correct
19	Correct	10 ms	49488 KB	Output is correct
20	Correct	8 ms	49488 KB	Output is correct
21	Incorrect	362 ms	49492 KB	Output isn't correct
22	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	49660 KB	Output is correct
3	Correct	8 ms	49488 KB	Output is correct
4	Correct	7 ms	49488 KB	Output is correct
5	Correct	8 ms	49660 KB	Output is correct
6	Correct	8 ms	49488 KB	Output is correct
7	Correct	9 ms	49488 KB	Output is correct
8	Correct	9 ms	49488 KB	Output is correct
9	Correct	8 ms	49488 KB	Output is correct
10	Correct	8 ms	49488 KB	Output is correct
11	Correct	13 ms	49656 KB	Output is correct
12	Correct	13 ms	49488 KB	Output is correct
13	Correct	16 ms	49488 KB	Output is correct
14	Correct	15 ms	49500 KB	Output is correct
15	Correct	12 ms	49488 KB	Output is correct
16	Correct	12 ms	49488 KB	Output is correct
17	Correct	12 ms	49488 KB	Output is correct
18	Correct	15 ms	49488 KB	Output is correct
19	Correct	10 ms	49488 KB	Output is correct
20	Correct	8 ms	49488 KB	Output is correct
21	Incorrect	362 ms	49492 KB	Output isn't correct
22	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	49660 KB	Output is correct
3	Correct	8 ms	49488 KB	Output is correct
4	Correct	7 ms	49488 KB	Output is correct
5	Correct	8 ms	49660 KB	Output is correct
6	Correct	8 ms	49488 KB	Output is correct
7	Correct	9 ms	49488 KB	Output is correct
8	Correct	9 ms	49488 KB	Output is correct
9	Correct	8 ms	49488 KB	Output is correct
10	Correct	8 ms	49488 KB	Output is correct
11	Correct	13 ms	49656 KB	Output is correct
12	Correct	13 ms	49488 KB	Output is correct
13	Correct	16 ms	49488 KB	Output is correct
14	Correct	15 ms	49500 KB	Output is correct
15	Correct	12 ms	49488 KB	Output is correct
16	Correct	12 ms	49488 KB	Output is correct
17	Correct	12 ms	49488 KB	Output is correct
18	Correct	15 ms	49488 KB	Output is correct
19	Correct	10 ms	49488 KB	Output is correct
20	Correct	8 ms	49488 KB	Output is correct
21	Incorrect	362 ms	49492 KB	Output isn't correct
22	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	49660 KB	Output is correct
3	Correct	8 ms	49488 KB	Output is correct
4	Correct	7 ms	49488 KB	Output is correct
5	Correct	8 ms	49660 KB	Output is correct
6	Correct	8 ms	49488 KB	Output is correct
7	Correct	9 ms	49488 KB	Output is correct
8	Correct	9 ms	49488 KB	Output is correct
9	Correct	8 ms	49488 KB	Output is correct
10	Correct	8 ms	49488 KB	Output is correct
11	Correct	13 ms	49656 KB	Output is correct
12	Correct	13 ms	49488 KB	Output is correct
13	Correct	16 ms	49488 KB	Output is correct
14	Correct	15 ms	49500 KB	Output is correct
15	Correct	12 ms	49488 KB	Output is correct
16	Correct	12 ms	49488 KB	Output is correct
17	Correct	12 ms	49488 KB	Output is correct
18	Correct	15 ms	49488 KB	Output is correct
19	Correct	10 ms	49488 KB	Output is correct
20	Correct	8 ms	49488 KB	Output is correct
21	Incorrect	362 ms	49492 KB	Output isn't correct
22	Halted	0 ms	0 KB	-