Submission #877012

#	Time	Username	Problem	Language	Result	Execution time	Memory
877012		pera	Bootfall (IZhO17_bootfall)	C++17	65 / 100	1050 ms	12844 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N = 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;
	vector<bitset<N>> dp(n + 1);
	for(int i = 0;i <= n;i ++){
		dp[i][0] = 1;
	}
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		s += a[i];
		dp[0] |= (dp[0] << a[i]);
		for(int p = 1;p <= n;p ++){
			if(p != i) dp[p] |= (dp[p] << 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:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0;i < ans.size();i ++){
      |                ~~^~~~~~~~~~~~

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