Submission #930920

#	Time	Username	Problem	Language	Result	Execution time	Memory
930920		OAleksa	Bootfall (IZhO17_bootfall)	C++14	65 / 100	675 ms	8336 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int N = 510;
const int A = 510;
const int M = N * A / 2;
bitset<125069> bt[N], sv;
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;
  	}
  	s /= 2;
  	for (int j = 1;j <= n;j++) {
  		bitset<125069> t;
  		t[0] = 1;
  		for (int i = 1;i <= n;i++) {
  			if (i == j)
  				continue;
  			t |= (t << a[i]);
  		}
  		bt[j] = t;
  	}
  	vector<int> ans;
  	for (int i = 1;i < M;i++) {
  		int ok = 1;
  		for (int j = 1;j <= n;j++) {
  			int r = i - a[j];
  			if (r & 1) {
  				ok = 0;
  				break;
  			}
  			r /= 2;
  			int x = s + r;
  			if (x > M || bt[j][x] == 0) {
  				ok = 0;
  				break;
  			}
  		}
  		if (ok)
  			ans.push_back(i);
  	}
  	cout << ans.size() << '\n';
  	for (auto i : ans)
  		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: 0 / 35