Submission #335547

#	Time	Username	Problem	Language	Result	Execution time	Memory
335547		luciocf	Bootfall (IZhO17_bootfall)	C++14	13 / 100	97 ms	2796 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

const int maxn = 510;
const int maxs = 250010;
const int mod = 1e9+7;

int a[maxn];
int dp[maxs], qtd[maxs];

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

	int s = 0;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		s += a[i];
	}

	dp[0] = 1;

	for (int i = 1; i <= n; i++)
		for (int j = maxs-1; j >= a[i]; j--)
			dp[j] += dp[j - a[i]];

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

	for (int i = 1; i <= n; i++)
	{
		for (int j = a[i]; j < maxs; j++)
			dp[j] = (dp[j] - dp[j - a[i]] + mod)%mod;

		for (int j = (s-a[i]+1)/2; j < maxs; j++)
			if (dp[j])
				qtd[2*j-s+a[i]]++;

		for (int j = maxs; j >= a[i]; j--)
			dp[j] = (dp[j] + dp[j - a[i]])%mod;
	}

	int ans = 0;
	for (int i = 1; i < maxs; i++)
		if (qtd[i] == n)
			ans++;

	printf("%d\n", ans);
	for (int i = 1; i < maxs; i++)
		if (qtd[i] == n)
			printf("%d ", i);
	printf("\n");
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bootfall.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~

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