제출 #1165084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165084		goats_9	Bootfall (IZhO17_bootfall)	C++20	100 / 100	745 ms	1064 KiB

bootfall

/* Author: goats_9 */

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int N = 500 * 250 + 1;
constexpr int M = 500 * 500 + 1;

int main() {
	cin.tie(0)->sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n);
	for (auto &u : a)
		cin >> u;
	int tot = accumulate(a.begin(), a.end(), 0);
	auto get = [&] (int ban) {
		bitset<N> ret;
		ret[0] = 1;
		for (int i = 0; i < n; i++) {
			if (i == ban) continue;
			ret |= ret << a[i];
		}
		return ret;
	};
	auto ini = get(-1);
	if (tot % 2 || !ini[tot / 2]) {
		return cout << "0", 0;
	}
	bitset<M> df;
	df.set();
	for (int i = 0; i < n; i++) {
		auto bst = get(i);
		bitset<M> ndf;
		for (int j = 0; 2 * j < tot - a[i]; j++) {
			if (bst[j]) ndf[tot - a[i] - 2 * j] = 1;
		}
		df &= ndf;
	}
	cout << df.count() << '\n';
	for (int i = 1; i < M; i++)
		if (df[i]) cout << i << ' ';
	return 0;
}

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