답안 #925217

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

# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -
# 결과 실행 시간 메모리 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 -