Submission #887961

#	Time	Username	Problem	Language	Result	Execution time	Memory
887961		alex_2008	Bootfall (IZhO17_bootfall)	C++14	28 / 100	1008 ms	13336 KiB

bootfall

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_set>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <unordered_map>
#include <fstream>
#include <random>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 510;
const int M = 500010;
int a[N];
bitset <M> b[N];
bool ch[N][2 * M];
int main() {
	int n, sm = 0;
	cin >> n;
	bitset <M> w;
	w[0] = 1;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i] % 2 != a[1] % 2) {
			cout << "0\n";
			return 0;
		}
		w |= (w << a[i]);
		sm += a[i];
	}
	if (sm % 2 == 1) {
		cout << "0\n";
		return 0;
	}
	if (!w[sm / 2]) {
		cout << "0\n";
		return 0;
	}
	bitset <M> answ;
	answ.set();
	for (int i = 1; i <= n; i++) {
		b[i][250000] = 1;
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			b[i] = ((b[i] << a[j]) | (b[i] >> a[j]));
		}
		answ &= b[i];
	}
	vector <int> ans;
	for (int j = 250001; j <= 500000; j++) {
		if (answ[j]) ans.push_back(j - 250000);
	}
	cout << (int)ans.size() << "\n";
	for (auto it : ans) {
		cout << it << " ";
	}
	cout << "\n";
}

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