Submission #513712

#	Time	Username	Problem	Language	Result	Execution time	Memory
513712		Mazaalai	Bootfall (IZhO17_bootfall)	C++17	0 / 100	0 ms	204 KiB

bootfall

#include <bits/stdc++.h>
#define pb push_back
#define ALL(x) x.begin(),x.end()
using namespace std;
int n;
vector <int> nums, ans;
void print(vector<int>x) {
	for (auto el : x) cout << el << ' ';cout << '\n';
}
bool solve(vector <int> vals) {
	int sum = 0;
	for (int i = 0; i < n; i++) sum += vals[i];
	if (sum & 1) return 0;
	int tar = sum / 2;
	vector <vector <bool> > dp(n, vector <bool>(tar, 0));
	dp[0][vals[0]] = dp[0][0] = 1;
	// print(vals);
	for (int i = 1; i < n; i++) 
	for (int j = tar-1; j >= 0; j--) {
		if (!dp[i-1][j]) continue;
		dp[i][j] = 1;
		if (j + vals[i] > tar) continue;
		if (j + vals[i] == tar) {
			// cout <<"done\n";
			return 1;
		}
		dp[i][j+vals[i]] = 1;
	}
	return 0;
}
bool possible() {
	bool res = 1;
	// cout << nums.back() << '\n';
	vector <bool> vis(501, 0);
	for (int i = 0; i <= n && res; i++) { // n^3
		vector <int> cur;
		if (vis[nums[i]]) continue;
		vis[nums[i]] = 1;
		for (int j = 0; j <= n; j++) { 
			if (j == i) continue;
			cur.pb(nums[j]);
		}
		res &= solve(cur); //n^2
	}
	// cout << "HERE: " << res << '\n';
	return res;
}
signed main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		nums.pb(x);
	}
	int mx = 0;
	sort(ALL(nums));
	for (int i = 0; i < n-1; i++) mx += nums[i];

	for (int i = 1; i <= mx; i+=2) { // n^4
		nums.pb(i);
		if (possible()) ans.pb(i);
		nums.pop_back();
	}
	cout << ans.size() << '\n';
	for (auto el : ans) cout << el << ' '; cout << '\n';
}

Compilation message (stderr)

bootfall.cpp: In function 'void print(std::vector<int>)':
bootfall.cpp:8:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    8 |  for (auto el : x) cout << el << ' ';cout << '\n';
      |  ^~~
bootfall.cpp:8:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
    8 |  for (auto el : x) cout << el << ' ';cout << '\n';
      |                                      ^~~~
bootfall.cpp: In function 'int main()':
bootfall.cpp:70:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   70 |  for (auto el : ans) cout << el << ' '; cout << '\n';
      |  ^~~
bootfall.cpp:70:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   70 |  for (auto el : ans) cout << el << ' '; cout << '\n';
      |                                         ^~~~

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