Submission #335546

#	Time	Username	Problem	Language	Result	Execution time	Memory
335546		luciocf	Bootfall (IZhO17_bootfall)	C++14	100 / 100	272 ms	17260 KiB

bootfall

#include <bits/stdc++.h>

using namespace std;

const int maxn = 510;
const int maxs = 250010;

int a[maxn];
int s;

bitset<maxs> aux, bs[maxn];

void solve(int l, int r)
{
	if (l > r) return;

	int mid = (l+r)>>1;

	bitset<maxs> ant = aux;

	for (int i = l; i <= mid; i++)
		aux |= (aux<<a[i]);

	solve(mid+1, r);

	aux = ant;

	for (int i = r; i >= mid; i--)
		aux |= (aux<<a[i]);

	solve(l, mid-1);

	aux = ant;
	s -= a[mid];

	for (int i = l; i < mid; i++)
		aux |= (aux<<a[i]);

	for (int i = r; i > mid; i--)
		aux |= (aux<<a[i]);

	for (int i = (s+1)/2; i < maxs; i++)
		if (aux[i])
			bs[mid][2*i-s] = 1; 

	aux = ant;
	s += a[mid];
}

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

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

	aux[0] = 1;

	for (int i = 1; i <= n; i++)
		aux |= (aux<<a[i]);

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

	aux.reset();
	aux[0] = 1;
	solve(1, n);

	bitset<maxs> ans;

	for (int i = 1; i < maxs; i++)
		ans[i] = 1;

	for (int i = 1; i <= n; i++)
		ans &= bs[i];

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

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

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
bootfall.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |   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