Submission #344965

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
344965	2021-01-06T20:14:24 Z	_ani	Bootfall (IZhO17_bootfall)	C++17	13 / 100	646 ms	262148 KB

bootfall

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 100;
vector<int> a, ans;
int SUM;
int dp[N + 1][N + 1][N * N + 1];
int hrashq[N + 1][N * N + 1];
int main()
{
	int n;
	cin >> n;
	a.resize(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		SUM += a[i];
	}
	bool skzb = false;
	for (int jnj = 0; jnj < n; jnj++) {
		auto b = a;
		b.erase(b.begin() + jnj);
		for (int i = 0; i < n - 1; i++)
			for (int sum = 0; sum <= N * N; sum++) {
				if (i - 1 < 0)
					dp[jnj][i][0] = dp[jnj][i][b[i]] = 1;
				else {
					dp[jnj][i][sum] = max(dp[jnj][i][sum], dp[jnj][i - 1][sum]);
					if (sum - b[i] >= 0)
						dp[jnj][i][sum] = max(dp[jnj][i][sum], dp[jnj][i - 1][sum - b[i]]);
				}
				if (sum == SUM / 2 && dp[jnj][i][sum])skzb = true;
			}
	}
	if (SUM % 2)skzb = false;
	for (int i = 1; i <= N * N; i++)
	{
		bool ok = true;
		for (int jnj = 0; jnj < n; jnj++)
		{
			int cursum = i - a[jnj] + SUM;
			if (cursum % 2) {
				ok = false;
				break;
			}
			bool lavalava = false;
			for (int k = 0; k < n - 1; k++)
				if (dp[jnj][k][cursum / 2] == 1)
					lavalava = true;
			if (!lavalava)ok = false;
		}
		if (ok && skzb)ans.push_back(i);
	}
	cout << ans.size() << '\n';
	for (int a : ans)
		cout << a << ' ';
	return 0;
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	1388 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	748 KB	Output is correct
5	Correct	9 ms	5100 KB	Output is correct
6	Correct	4 ms	2284 KB	Output is correct
7	Correct	3 ms	1388 KB	Output is correct
8	Correct	10 ms	5228 KB	Output is correct
9	Correct	5 ms	3564 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	1388 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	748 KB	Output is correct
5	Correct	9 ms	5100 KB	Output is correct
6	Correct	4 ms	2284 KB	Output is correct
7	Correct	3 ms	1388 KB	Output is correct
8	Correct	10 ms	5228 KB	Output is correct
9	Correct	5 ms	3564 KB	Output is correct
10	Correct	59 ms	33536 KB	Output is correct
11	Correct	61 ms	33644 KB	Output is correct
12	Correct	61 ms	33516 KB	Output is correct
13	Correct	35 ms	25088 KB	Output is correct
14	Correct	55 ms	29292 KB	Output is correct
15	Correct	60 ms	29164 KB	Output is correct
16	Correct	59 ms	33516 KB	Output is correct
17	Correct	18 ms	11756 KB	Output is correct
18	Correct	33 ms	21228 KB	Output is correct
19	Correct	41 ms	25216 KB	Output is correct
20	Correct	62 ms	33648 KB	Output is correct

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	1388 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	748 KB	Output is correct
5	Correct	9 ms	5100 KB	Output is correct
6	Correct	4 ms	2284 KB	Output is correct
7	Correct	3 ms	1388 KB	Output is correct
8	Correct	10 ms	5228 KB	Output is correct
9	Correct	5 ms	3564 KB	Output is correct
10	Correct	59 ms	33536 KB	Output is correct
11	Correct	61 ms	33644 KB	Output is correct
12	Correct	61 ms	33516 KB	Output is correct
13	Correct	35 ms	25088 KB	Output is correct
14	Correct	55 ms	29292 KB	Output is correct
15	Correct	60 ms	29164 KB	Output is correct
16	Correct	59 ms	33516 KB	Output is correct
17	Correct	18 ms	11756 KB	Output is correct
18	Correct	33 ms	21228 KB	Output is correct
19	Correct	41 ms	25216 KB	Output is correct
20	Correct	62 ms	33648 KB	Output is correct
21	Correct	507 ms	156416 KB	Output is correct
22	Correct	646 ms	209772 KB	Output is correct
23	Correct	293 ms	94956 KB	Output is correct
24	Runtime error	356 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

Subtask #4
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	1388 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	748 KB	Output is correct
5	Correct	9 ms	5100 KB	Output is correct
6	Correct	4 ms	2284 KB	Output is correct
7	Correct	3 ms	1388 KB	Output is correct
8	Correct	10 ms	5228 KB	Output is correct
9	Correct	5 ms	3564 KB	Output is correct
10	Correct	59 ms	33536 KB	Output is correct
11	Correct	61 ms	33644 KB	Output is correct
12	Correct	61 ms	33516 KB	Output is correct
13	Correct	35 ms	25088 KB	Output is correct
14	Correct	55 ms	29292 KB	Output is correct
15	Correct	60 ms	29164 KB	Output is correct
16	Correct	59 ms	33516 KB	Output is correct
17	Correct	18 ms	11756 KB	Output is correct
18	Correct	33 ms	21228 KB	Output is correct
19	Correct	41 ms	25216 KB	Output is correct
20	Correct	62 ms	33648 KB	Output is correct
21	Correct	507 ms	156416 KB	Output is correct
22	Correct	646 ms	209772 KB	Output is correct
23	Correct	293 ms	94956 KB	Output is correct
24	Runtime error	356 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	1388 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	748 KB	Output is correct
5	Correct	9 ms	5100 KB	Output is correct
6	Correct	4 ms	2284 KB	Output is correct
7	Correct	3 ms	1388 KB	Output is correct
8	Correct	10 ms	5228 KB	Output is correct
9	Correct	5 ms	3564 KB	Output is correct
10	Correct	59 ms	33536 KB	Output is correct
11	Correct	61 ms	33644 KB	Output is correct
12	Correct	61 ms	33516 KB	Output is correct
13	Correct	35 ms	25088 KB	Output is correct
14	Correct	55 ms	29292 KB	Output is correct
15	Correct	60 ms	29164 KB	Output is correct
16	Correct	59 ms	33516 KB	Output is correct
17	Correct	18 ms	11756 KB	Output is correct
18	Correct	33 ms	21228 KB	Output is correct
19	Correct	41 ms	25216 KB	Output is correct
20	Correct	62 ms	33648 KB	Output is correct
21	Correct	507 ms	156416 KB	Output is correct
22	Correct	646 ms	209772 KB	Output is correct
23	Correct	293 ms	94956 KB	Output is correct
24	Runtime error	356 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	1388 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	748 KB	Output is correct
5	Correct	9 ms	5100 KB	Output is correct
6	Correct	4 ms	2284 KB	Output is correct
7	Correct	3 ms	1388 KB	Output is correct
8	Correct	10 ms	5228 KB	Output is correct
9	Correct	5 ms	3564 KB	Output is correct
10	Correct	59 ms	33536 KB	Output is correct
11	Correct	61 ms	33644 KB	Output is correct
12	Correct	61 ms	33516 KB	Output is correct
13	Correct	35 ms	25088 KB	Output is correct
14	Correct	55 ms	29292 KB	Output is correct
15	Correct	60 ms	29164 KB	Output is correct
16	Correct	59 ms	33516 KB	Output is correct
17	Correct	18 ms	11756 KB	Output is correct
18	Correct	33 ms	21228 KB	Output is correct
19	Correct	41 ms	25216 KB	Output is correct
20	Correct	62 ms	33648 KB	Output is correct
21	Correct	507 ms	156416 KB	Output is correct
22	Correct	646 ms	209772 KB	Output is correct
23	Correct	293 ms	94956 KB	Output is correct
24	Runtime error	356 ms	262148 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Halted	0 ms	0 KB	-

Submission #344965

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