Submission #696988

#	Time	Username	Problem	Language	Result	Execution time	Memory
696988		allllekssssa	Bootfall (IZhO17_bootfall)	C++14	44 / 100	1020 ms	11776 KiB

bootfall

#include<bits/stdc++.h>
 
using namespace std;
 
const int maxN = 350 + 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;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35