Submission #949404

#	Time	Username	Problem	Language	Result	Execution time	Memory
949404		hqminhuwu	Bootfall (IZhO17_bootfall)	C++14	100 / 100	446 ms	31824 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

const int N = 5e2 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
const int lmt = 250001;

bitset <lmt> res, pre[N], suf[N], tmp;
int n, a[N], sum, cnt[4];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	#ifdef hqm
		freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
	#endif

	cin >> n;
	forr (i, 1, n)
		cin >> a[i], sum += a[i], cnt[a[i] & 1]++;
	
	pre[0][0] = 1;
	suf[n + 1][0] = 1;
	forr (i, 1, n)	pre[i] = pre[i - 1] | (pre[i - 1] << a[i]);
	ford (i, n, 1)	suf[i] = suf[i + 1] | (suf[i + 1] << a[i]);

	if (sum % 2 || !pre[n][sum / 2] || min(cnt[0], cnt[1]) > 0){
		cout << 0;
		return 0;
	}

	res.set();

	forr (i, 1, n){
		if (i * 2 <= n){
			tmp = suf[i + 1];
			ford (j, i - 1, 1)
				tmp |= tmp << a[j];
		}
		else {
			tmp = pre[i - 1];
			forr (j, i + 1, n)
				tmp |= tmp << a[j];
		}

		int nsum = sum - a[i];
		if (cnt[0])
			res &= tmp >> (nsum / 2);
		else res &= tmp >> (nsum / 2 + 1);
	}
	
	if (cnt[0])
		res[0] = 0;
		
	cout << res.count() << "\n";
	forf (i, 0, lmt){
		if (res[i])
			cout << i * 2 + (cnt[1] != 0) << " ";
	}
	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