Submission #36836

#	Time	Username	Problem	Language	Result	Execution time	Memory
36836		szawinis	Bootfall (IZhO17_bootfall)	C++14	100 / 100	836 ms	8728 KiB

bootfall

#include <bits/stdc++.h>
using namespace std;
const int N = 501, M = 3e5+1;

int n, sum, a[N], cnt[M];
long long dp[M], tmp[M];
int main() {
	scanf("%d", &n);
	dp[0] = 1;
	for(int i = 0; i < n; i++) {
		scanf("%d", a+i);
		sum += a[i];
		for(int j = M-1; j >= a[i]; j--) dp[j] += dp[j - a[i]];
	}
	if(sum % 2 || !dp[sum >> 1]) printf("0"), exit(0);
	for(int i = 0; i < n; i++) {
		copy(dp, dp+M, tmp);
		for(int j = a[i]; j < M; j++) tmp[j] -= tmp[j - a[i]]; // pay attention to order, only want to remove ones invalidated, not all combinations
		for(int x = 0; x < M; x++) {
			int val = sum - a[i] + x; // new sum of entire sequence including n+1
			cnt[x] += val % 2 == 0 && tmp[val >> 1];
		}
	}
	vector<int> ans;
	for(int x = 0; x < M; x++) if(cnt[x] == n) ans.push_back(x);
	printf("%d\n", ans.size());
	for(int x: ans) printf("%d ", x);
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:26:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", ans.size());
                           ^
bootfall.cpp:8:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
bootfall.cpp:11:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a+i);
                   ^

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