oj.uz

Submission #513713

# Submission time Handle Problem Language Result Execution time Memory
513713 2022-01-17T12:42:13 Z Mazaalai Bootfall (IZhO17_bootfall) C++17
0 / 100
 0 ms 204 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -