제출 #513717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
513717		Mazaalai	Bootfall (IZhO17_bootfall)	C++17	13 / 100	1092 ms	316 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;
}
int gcd(int a, int b) {
	if (a == 0) return b;
	return gcd(b%a, a);
}
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 ggcd = nums[0];
	for (int i = 1; i < n; i++) ggcd = gcd(ggcd, nums[i]);
	for (auto & el : nums) {
		el /= ggcd;
		if (el % 2 == 0) {
			cout << "0\n";
			return 0;
		}
	}
	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*ggcd);
		nums.pop_back();
	}
	cout << ans.size() << '\n';
	for (auto el : ans) cout << el << ' '; cout << '\n';
}

컴파일 시 표준 에러 (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:83:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   83 |  for (auto el : ans) cout << el << ' '; cout << '\n';
      |  ^~~
bootfall.cpp:83:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   83 |  for (auto el : ans) cout << el << ' '; cout << '\n';
      |                                         ^~~~

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