Submission #877823

#	Time	Username	Problem	Language	Result	Execution time	Memory
877823		pera	Bootfall (IZhO17_bootfall)	C++17	100 / 100	332 ms	3984 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N = 500 * 500;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n , s = 0;cin >> n;
	vector<int> a(n + 1) , dp(N + 1) , ans(N + 1 , 1) , v;
	dp[0] = 1;
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		s += a[i];
		for(int x = N;x >= a[i];x --) dp[x] += dp[x - a[i]];
	}
	if(s % 2 || !dp[s / 2]){
		cout << 0 << endl;
		return 0;
	}
	for(int x = 1;x <= n;x ++){
		auto ndp = dp;
		for(int y = a[x];y <= N;y ++) ndp[y] -= ndp[y - a[x]];
		for(int y = 0;y <= N;y ++){
			if(!ndp[y]){
				int g = 2 * y + a[x] - s;
				if(1 <= g && g <= N) ans[g] = 0;
			}
		}
		for(int g = ((a[x] - s) & 1) ^ 1;g <= N;g += 2) ans[g] = 0;
	}
	for(int x = 1;x <= N;x ++){
		if(ans[x]) v.push_back(x);
	}
	cout << v.size() << endl;
	for(int i = 0;i < v.size();i ++){
		cout << v[i] << " ";
	}
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i = 0;i < v.size();i ++){
      |                ~~^~~~~~~~~~

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