Submission #879612

#TimeUsernameProblemLanguageResultExecution timeMemory
879612alex_2008Bootfall (IZhO17_bootfall)C++14
65 / 100
1088 ms100048 KiB
#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];
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;
	}
	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 <= sm; j++) {
			if (b[i][j]) {
				if (2 * j < sm) {
					ch[i][sm - 2 * j] = true;
				}
				else {
					ch[i][2 * j - sm] = true;
				}
			}
		}
		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";
}
#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...