Submission #873275

#	Time	Username	Problem	Language	Result	Execution time	Memory
873275		c2zi6	Bootfall (IZhO17_bootfall)	C++14	65 / 100	1096 ms	1216 KiB

bootfall

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}

const int MAXN = 100;

#pragma GCC optimize("O3")

const int MAXSUM = 500 * 500;
typedef bitset<MAXSUM+1> bit;

bit f(VI& v, int excludant = -1) {
	bit ans;
	ans[0] = 1;
	rep(i, v.size()) {
		if (i == excludant) continue;
		ans |= (ans << v[i]);
	}
	return ans;
}

void solve() {
	int n;
	cin >> n;
	VI a(n);
	int sum = 0;
	for (int& x : a) cin >> x, sum += x;

	bit pos = f(a);
	if (sum % 2 || !pos[sum/2]) cout << 0 << endl;
	else {
		bit ans = ~bit(0);
		rep(i, n) {
			bit pos = f(a, i);
			for (int x = 0; x <= MAXSUM; x++) {
				int newsum = (sum - a[i] + x);
				if (newsum % 2 || newsum/2 < x || (!pos[newsum/2] && !pos[newsum/2 - x])) {
					ans[x] = false;
				}
			}
		}
		VI v;
		for (int i = 0; i <= MAXSUM; i++) {
			if (ans[i]) v.pb(i);
		}
		cout << v.size() << endl;
		for (int x : v) cout << x << " ";
		cout << endl;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	solve();
}

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