Submission #514491

#	Time	Username	Problem	Language	Result	Execution time	Memory
514491		Mazaalai	Bootfall (IZhO17_bootfall)	C++17	28 / 100	1076 ms	1640 KiB

bootfall

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n, m;
const int N = 270+5;
const int M = 270*270 + 5;
const int K = M / 2;
vector <int> ans;
int nums[N], pre[K], suf[K], sum;
int gcd(int a, int b) {
	if (a == 0) return b;
	return gcd(b%a, a);
}
signed main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> nums[i];
	int ggcd = nums[1];
	for (int i = 2; i <= n; i++) ggcd = gcd(ggcd, nums[i]);
	for (int i = 1; i <= n; i++) {
		nums[i] /= ggcd;
		if (nums[i] % 2 == 0) {
			sum = 1;
			break;
		}
		sum += nums[i];
	}
	if (sum & 1 || n & 1) {
		cout << "0\n";
		return 0;
	}
	memset(pre, -1, sizeof(pre));
	memset(suf, -1, sizeof(suf));
	set <int> vals;
	pre[0] = 0;
	vals.insert(0);
	for (int i = 1; i <= n; i++) {
		vector <int> add;
		for (auto& el : vals) {
			int sum = el + nums[i];
			if (sum >= K || pre[sum] != -1) continue;
			pre[sum] = i;
			add.pb(sum);
		}
		for (auto& el : add) vals.insert(el);
	}
	vals.clear();
	suf[0] = n+1;
	vals.insert(0);
	for (int i = n; i > 0; i--) {
		vector <int> add;
		for (auto& el : vals) {
			int sum = el + nums[i];
			if (sum >= K || suf[sum] != -1) continue;
			suf[sum] = i;
			add.pb(sum);
		}
		for (auto& el : add) vals.insert(el);
	}
// for (int i = 1; i <= 50; i++) cout << pre[i] << " \n"[i==50];
// for (int i = 1; i <= 50; i++) cout << suf[i] << " \n"[i==50];
	for (int i = 1; i <= sum; i++) {
		bool possible = 1;
		int totalSum = sum + i, target;
		if (totalSum % 2 == 0) continue;
		for (int j = 1; j <= n && possible; j++) {
			if (i > totalSum - nums[j]) {
				possible = 0;
				break;
			}
			target = (totalSum - nums[j]) / 2;
			bool cur = 0;
			for (int k = 0; k * 2 <= target && !cur; k++) {
				if (pre[k] != -1 && suf[target-k] != -1)
					cur |= (pre[k] < j && j < suf[target-k]);
				if (suf[k] != -1 && pre[target-k] != -1)
					cur |= (pre[target-k] < j && j < suf[k]);
			}
			possible &= cur;
		}
		if (possible) ans.pb(i);
	}



	cout << ans.size() << '\n';
	for (auto& el : ans) cout << el*ggcd << ' '; cout << '\n';
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:91:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   91 |  for (auto& el : ans) cout << el*ggcd << ' '; cout << '\n';
      |  ^~~
bootfall.cpp:91:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   91 |  for (auto& el : ans) cout << el*ggcd << ' '; cout << '\n';
      |                                               ^~~~

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