oj.uz

Submission #768165

# Submission time Handle Problem Language Result Execution time Memory
768165 2023-06-27T15:50:09 Z rainboy Bootfall (IZhO17_bootfall) C
0 / 100
 1 ms 596 KB 
#include <stdio.h>

#define N	500
#define A	500
#define S	(N * A)
#define L	60
#define K	(S / L + 1)

int aa[N], kk[S + 1], n;
long long dp[N + 1][K]; int n_;

void add(int a) {
	int h, q, r;

	q = a / L, r = a % L;
	n_++;
	for (h = 0; h < K; h++) {
		dp[n_][h] = dp[n_ - 1][h];
		if (h >= q)
			dp[n_][h] |= (dp[n_ - 1][h - q] & (1LL << (L - r)) - 1) << r;
		if (h >= q + 1)
			dp[n_][h] |= dp[n_ - 1][h - q + 1] >> (L - r);
	}
}

void solve(int l, int r) {
	int m, i, s, sum;

	if (l == r) {
		sum = 0;
		for (i = 0; i < n; i++)
			if (i != l)
				sum += aa[i];
		for (s = 0; s * 2 <= sum; s++)
			if ((dp[n_][s / L] & 1LL << s % L) != 0)
				kk[sum - s * 2]++;
		return;
	}
	m = (l + r) / 2;
	for (i = m + 1; i <= r; i++)
		add(aa[i]);
	solve(l, m);
	n_ -= r - m;
	for (i = l; i <= m; i++)
		add(aa[i]);
	solve(m + 1, r);
	n_ -= m - l + 1;
}

int main() {
	int i, sum, a, k;

	scanf("%d", &n);
	sum = 0;
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		sum += aa[i];
	}
	if (sum % 2 != 0) {
		printf("0\n\n");
		return 0;
	}
	dp[0][0] = 1, n_ = 0;
	for (i = 0; i < n; i++)
		add(aa[i]);
	if ((dp[n_][sum / 2 / L] & 1LL << sum / 2 % L) == 0) {
		printf("0\n\n");
		return 0;
	}
	n_ = 0, solve(0, n - 1);
	k = 0;
	for (a = 1; a <= S; a++)
		if (kk[a] == n)
			k++;
	printf("%d\n", k);
	for (a = 1; a <= S; a++)
		if (kk[a] == n)
			printf("%d ", a);
	printf("\n");
	return 0;
}

Compilation message

bootfall.c: In function 'add':
bootfall.c:20:55: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   20 |    dp[n_][h] |= (dp[n_ - 1][h - q] & (1LL << (L - r)) - 1) << r;
      |                                      ~~~~~~~~~~~~~~~~~^~~
bootfall.c: In function 'main':
bootfall.c:53:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
bootfall.c:56:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -