답안 #925217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
925217	2024-02-11T05:05:32 Z	atom	Bootfall (IZhO17_bootfall)	C++17	13 / 100	41 ms	3676 KB

bootfall

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 501 * 501;
int n;
int a[N];

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    #ifdef JASPER
        freopen("in1", "r", stdin);
    #endif

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    int sz = accumulate(a + 1, a + 1 + n, 0);
	
	// dp(x) : number of ways constructing sum equal to x;
	vector <int> dp1(N, 0), dp2(N, 0), able(N, 1);
	dp1[0] = 1;

	// solving first case: a[0] is the observer
	// -> use first case to solve others
	for (int i = 1; i <= n; ++i)
		for (int j = sz; j >= a[i]; --j)
			dp1[j] += dp1[j - a[i]];

	if ((sz & 1) || !dp1[sz / 2]) {
		cout << "0\n";
		return 0;
	}


	auto solve = [&] (int id) -> void {
		for (int i = 0; i < N; ++i) dp2[i] = dp1[i];
		for (int j = a[id]; j < N; ++j)
			dp2[j] -= dp2[j - a[id]];
		// choose value
		for (int x = 1; x < N; ++x) {
			int new_sz = sz - a[id] + x;
			if ((new_sz & 1) || (new_sz / 2 < x) || dp2[(new_sz / 2) - x] <= 0)
				able[x] = 0;
		}
	};
	

	for (int i = 1; i <= n; ++i) {
		// debug(able[3]);
		solve(i);
	}

	vector <int> ans;
	for (int x = 1; x < N; ++x) {
		if (able[x]) {
			ans.push_back(x);
		}
	}

	cout << (int) (ans.size()) << "\n";
	for (int x : ans) cout << x << " ";
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3416 KB	Output is correct
2	Correct	5 ms	3420 KB	Output is correct
3	Correct	2 ms	3420 KB	Output is correct
4	Correct	5 ms	3420 KB	Output is correct
5	Correct	8 ms	3420 KB	Output is correct
6	Correct	6 ms	3420 KB	Output is correct
7	Correct	5 ms	3420 KB	Output is correct
8	Correct	8 ms	3420 KB	Output is correct
9	Correct	7 ms	3420 KB	Output is correct

Subtask #2
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3416 KB	Output is correct
2	Correct	5 ms	3420 KB	Output is correct
3	Correct	2 ms	3420 KB	Output is correct
4	Correct	5 ms	3420 KB	Output is correct
5	Correct	8 ms	3420 KB	Output is correct
6	Correct	6 ms	3420 KB	Output is correct
7	Correct	5 ms	3420 KB	Output is correct
8	Correct	8 ms	3420 KB	Output is correct
9	Correct	7 ms	3420 KB	Output is correct
10	Correct	20 ms	3676 KB	Output is correct
11	Correct	17 ms	3420 KB	Output is correct
12	Correct	16 ms	3420 KB	Output is correct
13	Correct	15 ms	3416 KB	Output is correct
14	Correct	15 ms	3420 KB	Output is correct
15	Correct	16 ms	3428 KB	Output is correct
16	Correct	17 ms	3420 KB	Output is correct
17	Correct	11 ms	3420 KB	Output is correct
18	Correct	14 ms	3428 KB	Output is correct
19	Correct	16 ms	3424 KB	Output is correct
20	Correct	16 ms	3416 KB	Output is correct

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3416 KB	Output is correct
2	Correct	5 ms	3420 KB	Output is correct
3	Correct	2 ms	3420 KB	Output is correct
4	Correct	5 ms	3420 KB	Output is correct
5	Correct	8 ms	3420 KB	Output is correct
6	Correct	6 ms	3420 KB	Output is correct
7	Correct	5 ms	3420 KB	Output is correct
8	Correct	8 ms	3420 KB	Output is correct
9	Correct	7 ms	3420 KB	Output is correct
10	Correct	20 ms	3676 KB	Output is correct
11	Correct	17 ms	3420 KB	Output is correct
12	Correct	16 ms	3420 KB	Output is correct
13	Correct	15 ms	3416 KB	Output is correct
14	Correct	15 ms	3420 KB	Output is correct
15	Correct	16 ms	3428 KB	Output is correct
16	Correct	17 ms	3420 KB	Output is correct
17	Correct	11 ms	3420 KB	Output is correct
18	Correct	14 ms	3428 KB	Output is correct
19	Correct	16 ms	3424 KB	Output is correct
20	Correct	16 ms	3416 KB	Output is correct
21	Incorrect	41 ms	3420 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3416 KB	Output is correct
2	Correct	5 ms	3420 KB	Output is correct
3	Correct	2 ms	3420 KB	Output is correct
4	Correct	5 ms	3420 KB	Output is correct
5	Correct	8 ms	3420 KB	Output is correct
6	Correct	6 ms	3420 KB	Output is correct
7	Correct	5 ms	3420 KB	Output is correct
8	Correct	8 ms	3420 KB	Output is correct
9	Correct	7 ms	3420 KB	Output is correct
10	Correct	20 ms	3676 KB	Output is correct
11	Correct	17 ms	3420 KB	Output is correct
12	Correct	16 ms	3420 KB	Output is correct
13	Correct	15 ms	3416 KB	Output is correct
14	Correct	15 ms	3420 KB	Output is correct
15	Correct	16 ms	3428 KB	Output is correct
16	Correct	17 ms	3420 KB	Output is correct
17	Correct	11 ms	3420 KB	Output is correct
18	Correct	14 ms	3428 KB	Output is correct
19	Correct	16 ms	3424 KB	Output is correct
20	Correct	16 ms	3416 KB	Output is correct
21	Incorrect	41 ms	3420 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3416 KB	Output is correct
2	Correct	5 ms	3420 KB	Output is correct
3	Correct	2 ms	3420 KB	Output is correct
4	Correct	5 ms	3420 KB	Output is correct
5	Correct	8 ms	3420 KB	Output is correct
6	Correct	6 ms	3420 KB	Output is correct
7	Correct	5 ms	3420 KB	Output is correct
8	Correct	8 ms	3420 KB	Output is correct
9	Correct	7 ms	3420 KB	Output is correct
10	Correct	20 ms	3676 KB	Output is correct
11	Correct	17 ms	3420 KB	Output is correct
12	Correct	16 ms	3420 KB	Output is correct
13	Correct	15 ms	3416 KB	Output is correct
14	Correct	15 ms	3420 KB	Output is correct
15	Correct	16 ms	3428 KB	Output is correct
16	Correct	17 ms	3420 KB	Output is correct
17	Correct	11 ms	3420 KB	Output is correct
18	Correct	14 ms	3428 KB	Output is correct
19	Correct	16 ms	3424 KB	Output is correct
20	Correct	16 ms	3416 KB	Output is correct
21	Incorrect	41 ms	3420 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #6
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	3416 KB	Output is correct
2	Correct	5 ms	3420 KB	Output is correct
3	Correct	2 ms	3420 KB	Output is correct
4	Correct	5 ms	3420 KB	Output is correct
5	Correct	8 ms	3420 KB	Output is correct
6	Correct	6 ms	3420 KB	Output is correct
7	Correct	5 ms	3420 KB	Output is correct
8	Correct	8 ms	3420 KB	Output is correct
9	Correct	7 ms	3420 KB	Output is correct
10	Correct	20 ms	3676 KB	Output is correct
11	Correct	17 ms	3420 KB	Output is correct
12	Correct	16 ms	3420 KB	Output is correct
13	Correct	15 ms	3416 KB	Output is correct
14	Correct	15 ms	3420 KB	Output is correct
15	Correct	16 ms	3428 KB	Output is correct
16	Correct	17 ms	3420 KB	Output is correct
17	Correct	11 ms	3420 KB	Output is correct
18	Correct	14 ms	3428 KB	Output is correct
19	Correct	16 ms	3424 KB	Output is correct
20	Correct	16 ms	3416 KB	Output is correct
21	Incorrect	41 ms	3420 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

답안 #925217

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