제출 #696987

#제출 시각아이디문제언어결과실행 시간메모리
696987allllekssssaBootfall (IZhO17_bootfall)C++14
44 / 100
310 ms5712 KiB
#include<bits/stdc++.h>

using namespace std;

const int maxN = 270 + 5;
const int bsSize = maxN * maxN + 10;
int n;
int a[maxN];
bitset<bsSize> dp[2][maxN];

int main() {

	cin >> n;
    
	int sum = 0;

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

	for (int i = 1; i <= n + 1; i++) {
		dp[0][i].set(0);
	}

	for (int i = 1; i<=n; i++) {
		for (int j = 1; j <= n + 1; j++) {
			if (i == j) {
				dp[i&1][j] = dp[(i&1) ^ 1][j];
			} else {
				dp[i&1][j] = dp[(i&1) ^ 1][j] | (dp[(i&1) ^ 1][j] << a[i]);
			}
		}

		for (int j = 1; j<= n + 1; j++) {
			dp[(i - 1)&1][j].reset();
		}
	}

	if (dp[n&1][n + 1][sum/2] == 0) {
		printf("0\n");
		return 0;
	}
    
    vector<int> ans;

	for (int i = 1; i <= sum; i++) {
		bool ok = true;
         
        for (int j = 1; j<= n; j++) {
        	int totSum = sum  - a[j] + i;
        	if (totSum % 2 == 1) ok = false;
        	if (dp[n&1][j][totSum/2] == 0) ok = false;
        }

		if (ok) ans.push_back(i);
	}

	cout << ans.size() << endl;

	for (int i:ans) {
		cout << i << " ";
	}

	cout << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...