Submission #670155

#	Time	Username	Problem	Language	Result	Execution time	Memory
670155		mychecksedad	Bootfall (IZhO17_bootfall)	C++17	65 / 100	558 ms	4908 KiB

bootfall

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 510, M = 501, 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;
	}


	vector<int> mn(M, M);

	vector<int> s;
	s.pb(0);
	for(int i = 1; i <= n; ++i){
		mn[a[i]] = min(i, mn[a[i]]);
		if(mn[a[i]] == i) s.pb(i);
	}


	for(int i: s){
		dp[i][0] = 1;
		for(int l = 1; l <= n; ++l){
			if(i == l) continue;
			dp[i] = dp[i] | (dp[i] << a[l]);
		}
	}

	vector<int> possible;

	for(int x = 2 - (a[1] % 2); x < MX; x += 2){	
		ok = 1;
		a[0] = x;
		for(int i: s){
			bool state1 = 0, state2 = 0;
			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: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 0 / 35