Submission #670121

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670121	2022-12-08T07:23:34 Z	mychecksedad	Bootfall (IZhO17_bootfall)	C++17	0 / 100	1 ms	340 KB

bootfall

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

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 || (n % 2 == 1 && a[1] % 2 == 1)){
		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; 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){
			int req = (S + x - a[i]) >> 1;
			if(req >= M * M || !dp[i][req]){
				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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Incorrect	1 ms	340 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Incorrect	1 ms	340 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Incorrect	1 ms	340 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #4

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Incorrect	1 ms	340 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #5

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Incorrect	1 ms	340 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #6

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Incorrect	1 ms	340 KB	Output isn't correct
6	Halted	0 ms	0 KB	-