Submission #670148

#	Time	Username	Problem	Language	Result	Execution time	Memory
670148		mychecksedad	Bootfall (IZhO17_bootfall)	C++17	0 / 100	1 ms	340 KiB

bootfall

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 510, M = 500, MX = 500*500/2 + 1;

int n, a[N], S = 0;
bitset<N*N/2> dp[N];
void solve(){
	cin >> n;
	bool ok = 1;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		S += a[i];
		if(a[i] % 2 != a[1] % 2){
			ok = 0;
		}
	}

	if(!ok || S % 2){
		cout << 0;
		return;
	}

	for(int i = 0; i <= n; ++i){
		dp[i][0] = 1;
		for(int l = 1; l <= n; ++l){
			if(i == l) continue;
			for(int j = M - a[l]; j >= 0; --j){
				dp[i][j + a[l]] = dp[i][j + a[l]] | (dp[i][j] << a[l]);
			}
		}
	}

	vector<int> possible;

	for(int x = 2 - (a[1] % 2); x <= M * M; x += 2){	
		ok = 1;
		a[0] = x;
		for(int i = 0; i <= n; ++i){
			bool state1 = 1, state2 = 1;
			if(i == 0){
				int req = (S + x - a[i]) >> 1;
				state1 = (req < MX && dp[i][req]);
			}else{
				int req = (S + x - a[i]) >> 1, req1 = ((S + x - a[i]) >> 1) - x;
				state1 = (req < MX && dp[i][req]);
				state2 = (req1 >= 0 && req1 < MX && dp[i][req1]);
			}
			if(!(state1 | state2)){
				ok = 0;
				break;
			}
		}
		if(ok){
			possible.pb(x);
		}

	}

	cout << possible.size() << '\n';
	for(int p: possible) cout << p << ' ';
}




int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    solve();
    return 0;
 
}

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