Submission #930948

#	Time	Username	Problem	Language	Result	Execution time	Memory
930948		OAleksa	Bootfall (IZhO17_bootfall)	C++14	100 / 100	405 ms	32088 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 510;
const int A = 510;
bitset<250069> sf[N], sv, ans, pr[N], even, odd;
int n, a[N];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
  	cin >> n;
  	sv[0] = 1;
  	for (int i = 1;i <= n;i++)
  		cin >> a[i], sv |= (sv << a[i]);
  	int s = accumulate(a + 1, a + n + 1, 0);
  	if (s % 2 == 1 || sv[s / 2] == 0) {
  		cout << '0';
  		return 0;
  	}
  	pr[0][0] = 1;
  	for (int i = 1;i <= n;i++) 
  		pr[i] = pr[i - 1] | (pr[i - 1] << a[i]);
  	sf[n + 1][0] = 1;
  	for (int i = n;i >= 1;i--)
  		sf[i] = sf[i + 1] | (sf[i + 1] << a[i]);
  	even.set();
  	odd.set();
		bitset<250069> cur;
		for (int i = 1;i <= n;i++) {
			if (i > n / 2) {
				cur = pr[i - 1];
				for (int j = i + 1;j <= n;j++)
					cur |= (cur << a[j]);
			}
			else {
				cur = sf[i + 1];
				for (int j = i - 1;j > 0;j--) 
					cur |= (cur << a[j]);
			}
			int l = s - a[i];
			if (l % 2 == 0) {
				//j mora bude parno
				even &= (cur >> (l / 2));
				odd &= 0;
			}
			else {
				odd &= (cur >> ((l + 1) / 2));
				even &= 0;
			}
		}
  	cout << even.count() + odd.count() << '\n';
  	for (int i = 0;i < 250069;i++) {
  		if (even[i])
  			cout << 2 * i << ' ';
  		else if (odd[i])
  			cout << 2 * i + 1 << ' ';
  	}
  }
  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