Submission #335548

#	Time	Username	Problem	Language	Result	Execution time	Memory
335548		luciocf	Bootfall (IZhO17_bootfall)	C++14	100 / 100	720 ms	3024 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] + dp[j - a[i]])%mod;
 
	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: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 35 / 35