Submission #879607

#	Time	Username	Problem	Language	Result	Execution time	Memory
879607		alex_2008	Bootfall (IZhO17_bootfall)	C++14	44 / 100	1029 ms	25432 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 = 251000;
int a[N];
bitset <M> b[N];
bitset <M> ch[N];
int main() {
          ios_base::sync_with_stdio(false); cin.tie(0);
	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;
	}
	for (int i = 1; i <= n; i++) {
		b[i][0] = 1;
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			b[i] |= (b[i] << a[j]);
		}
	}
	for (int i = 1; i <= n; i++) {
		sm -= a[i];
		for (int j = 0; j <= 250000; j++) {
			if (b[i][j]) {
				if (2 * j < sm) {
					ch[i][sm - 2 * j] = 1;
				}
				else {
					ch[i][2 * j - sm] = 1;
				}
			}
		}
		sm += a[i];
	}
	vector <int> ans;
	for (int j = 1; j <= 250000; j++) {
		bool flag = true;
		for (int i = 1; i <= n; i++) {
			if (ch[i][j]) continue;
			flag = false; break;
		}
		if (flag) ans.push_back(j);
	}
	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: 16 / 16
• Subtask 5: 0 / 21
• Subtask 6: 0 / 35