Submission #671940

#	Time	Username	Problem	Language	Result	Execution time	Memory
671940		viwlesxq	Bootfall (IZhO17_bootfall)	C++17	100 / 100	237 ms	4352 KiB

bootfall

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef string str;

#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
void freo(str x) {freopen((x + ".in").c_str(), "r", stdin);freopen((x + ".out").c_str(), "w", stdout);}

const int MAXN = 500, MAXSUM = 250001;
ll dp[MAXSUM];
int used[MAXSUM];
vector <int> ans;
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	int sum = 0, a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	dp[0]++;
	if (sum % 2) {
		cout << 0;
		return 0;
	}
	for (int i = 0; i < n; i++) {
		for (int j = sum; j - a[i] >= 0; j--) {
			dp[j] += dp[j - a[i]];
		}
	}
	if (!dp[sum / 2]) {
		cout << 0;
		return 0;
	}
	for (int i = 0; i < n; i++) {
		int cur = sum - a[i];
		for (int j = a[i]; j <= sum; j++) {
			dp[j] -= dp[j - a[i]];
		}
		for (int j = 0; j <= cur / 2; j++) {
			if (dp[j]) used[cur - j * 2]++;
		}
		for (int j = sum; j >= a[i]; j--) {
			dp[j] += dp[j - a[i]];
		}
	}
	for (int i = 0; i <= sum; i++) {
		if (used[i] == n) ans.pb(i);
	}
	cout << sz(ans) << '\n';
	for (int i : ans) cout << i << ' ';
}

Compilation message (stderr)

bootfall.cpp: In function 'void freo(str)':
bootfall.cpp:21:26: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 | void freo(str x) {freopen((x + ".in").c_str(), "r", stdin);freopen((x + ".out").c_str(), "w", stdout);}
      |                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:21:67: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 | void freo(str x) {freopen((x + ".in").c_str(), "r", stdin);freopen((x + ".out").c_str(), "w", stdout);}
      |                                                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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