Submission #35048

#	Time	Username	Problem	Language	Result	Execution time	Memory
35048		model_code	Bootfall (IZhO17_bootfall)	C++11	13 / 100	1000 ms	2528 KiB

bootfall

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>

#define ll long long
#define pb push_back
#define f first
#define s second
#define mp make_pair

using namespace std;

const int maxn = 5e2 + 11;

int n, a[maxn], s;
bool dp[2 * maxn * maxn];

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		s += a[i];
	}

	if (s % 2 != 0) {
		cout << 0;
		return 0;
	}

	dp[0] = 1;
	s /= 2;

	for (int i = 0; i < n; ++i)
	for (int sum = s; sum >= 0; --sum)
		if (dp[sum] && sum + a[i] <= s) 
			dp[sum + a[i]] = 1;

	if (!dp[s]) {
		cout << 0;
		return 0;
	}

	vector < int > ans;

	for (int x = 0; x <= s + s; x++) {
	        bool ok = 1;

		for (int i = 0; i < n; ++i) {
       		        int curs = s + s - a[i] + x;
		        if (curs % 2 != 0) {
		        	ok = 0;
		        	break;
		        }
		        curs /= 2;
		        memset(dp, 0, sizeof(dp));
		        dp[0] = 1;

		        swap(a[i], x);
			
			for (int j = 0; j < n; ++j)
				for (int sum = curs; sum >= 0; --sum)
					if (dp[sum] && sum + a[j] <= curs) 
						dp[sum + a[j]] = 1;

			swap(a[i], x);
			
			if (!dp[curs]) {
				ok = 0;
				break;
			}
		}

		if (ok) 
			ans.pb(x);
	}

	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); ++i)
		cout << ans[i] << ' ';

	return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  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