Submission #768165

#TimeUsernameProblemLanguageResultExecution timeMemory
768165rainboyBootfall (IZhO17_bootfall)C11
0 / 100
1 ms596 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...