This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
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]);
| ^~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |