Submission #229857

#	Time	Username	Problem	Language	Result	Execution time	Memory
229857		pedroslrey	Bootfall (IZhO17_bootfall)	C++14	28 / 100	182 ms	9216 KiB

bootfall

//Bootfall subtask 1

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;
using lli = long long int;

#define debug(args...) fprintf(stderr, args)
#define pb push_back
#define fi first
#define se second
#define all(xs) xs.begin(), xs.end()

const int INF = 1e9;

int xs[110];
int dp[110][10010];

int marc[10010];

void make_dp(int n, int s, int ignore) {
	dp[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		for (int x = 0; x <= s; ++x) {
			if (i == ignore) {
				dp[i][x] = dp[i-1][x];
				continue;
			}
			int k = 0;
			if (x - xs[i] >= 0) k = dp[i-1][x - xs[i]];
			dp[i][x] = dp[i-1][x] || k;
		}
	}
}

void solve(int n) {
	int s = 0;
	for (int i = 1; i <= n; ++i)
		s += xs[i];

	make_dp(n, s, 0);
	if (!dp[n][s/2] || s%2 == 1) {
		printf("0\n");
		return;
	}

	for (int i = 1; i <= n; ++i) {
		make_dp(n, s, i);
		for (int k = 1; k <= s; ++k) {
			if ((s - xs[i] + k)%2 == 1) marc[k] = 0;
			if (dp[n][((s - xs[i] + k)/2 - k)]) ++marc[k];
		}
	}

	vector<int> ans;
	for (int k = 1; k <= s; ++k) 
		if (marc[k] == n) ans.pb(k);

	printf("%d\n", (int) ans.size());
	for (int a: ans) 
		printf("%d ", a);
	printf("\n");
}

int main() {
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; ++i)
		scanf("%d", &xs[i]);

	solve(n);
}

Compilation message (stderr)

bootfall.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
bootfall.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
bootfall.cpp: In function 'int main()':
bootfall.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bootfall.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &xs[i]);
   ~~~~~^~~~~~~~~~~~~~

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