Submission #877002

#	Time	Username	Problem	Language	Result	Execution time	Memory
877002		pera	Bootfall (IZhO17_bootfall)	C++17	13 / 100	1081 ms	74332 KiB

bootfall

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

Compilation message (stderr)

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

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