Submission #442126

#	Time	Username	Problem	Language	Result	Execution time	Memory
442126		Nima_Naderi	Bootfall (IZhO17_bootfall)	C++14	100 / 100	136 ms	3148 KiB

bootfall

//In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define md ((s + e) / 2)
#define dm ((s + e) / 2 + 1)
using namespace std;

typedef long long ll;
const ll MXN = 500 + 10;
const ll MXV = 25e4 + 10;
ll n, sum;
ll A[MXN], ANS[MXV];
bitset<MXV> inp;
void Upd(bitset<MXV> &bs, ll w){
	bs |= (bs << w);
}
void solve(ll s, ll e, const bitset<MXV> &old){
	if(s == e){
		sum -= A[s];
		//cout << "expect " << s << " : \n";
		for(int w = (sum + 1) / 2; w <= sum; w ++){
			if(old[w]){
				//cout << w << ' ';
				ANS[w - (sum - w)] ++;
			}
		}
		//cout << '\n';
		sum += A[s];
		return;
	}
	bitset<MXV> nw = old;
	for(int i = dm; i <= e; i ++) Upd(nw, A[i]);
	solve(s, md, nw);
	nw = old;
	for(int i = s; i <= md; i ++) Upd(nw, A[i]);
	solve(dm, e, nw);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> A[i], sum += A[i];
	inp[0] = 1;
	for(int i = 1; i <= n; i ++) Upd(inp, A[i]);
	if(sum % 2 == 1 || inp[sum / 2] == 0){
		cout << 0 << '\n';
		return 0;
	}
	for(int i = 0; i < MXV; i ++) inp[i] = 0;
	inp[0] = 1;
	solve(1, n, inp);
	ll ans = 0;
	for(int i = 0; i < MXV; i ++) ans += (ANS[i] == n);
	cout << ans << '\n';
	for(int i = 0; i < MXV; i ++){
		if(ANS[i] == n) cout << i << ' ';
	}
	cout << '\n';
	return 0;
}
//! N.N

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