Submission #471229

#TimeUsernameProblemLanguageResultExecution timeMemory
471229rainboySan (COCI17_san)C11
120 / 120
62 ms19500 KiB
#include <stdio.h> #define N 40 #define M (N / 2) int first[1 << M], last[1 << M]; void init() { int i, b; for (b = 1; b < 1 << M; b++) { i = 0; while ((b & 1 << i) == 0) i++; first[b] = i; i = M - 1; while ((b & 1 << i) == 0) i--; last[b] = i; } } void merge(long long *ww, int *uu, int n, int *vv, int m) { int i = n - 1, j = m - 1, k = n + m - 1; while (i >= 0 && j >= 0) uu[k--] = ww[uu[i]] > ww[vv[j]] ? uu[i--] : vv[j--]; while (i >= 0) uu[k--] = uu[i--]; while (j >= 0) uu[k--] = vv[j--]; } int main() { static int aa[N], bb[N], uu[1 << M], uu_[1 << M], vv[1 << M], vv_[1 << M], kk[M]; static long long ww[1 << M], xx[1 << M]; int n, m, h, h1, h2, i, k1, k1_, k2, k2_, u, v; long long l, ans; init(); scanf("%d%lld", &n, &l), m = n / 2; for (i = 0; i < n; i++) scanf("%d%d", &aa[i], &bb[i]); k1 = 0; uu[k1++] = 0; for (i = 0; i < m; i++) { k1_ = 0; for (h = 0; h < k1; h++) { u = uu[h]; if (u == 0 || aa[last[u]] <= aa[i]) ww[uu_[k1_++] = u | 1 << i] = ww[u] + bb[i]; } merge(ww, uu, k1, uu_, k1_), k1 += k1_; } k2 = 0; vv[k2++] = 0; for (i = m; i < n; i++) { k2_ = 0; for (h = 0; h < k2; h++) { v = vv[h]; if (v == 0 || aa[m + last[v]] <= aa[i]) xx[vv_[k2_++] = v | 1 << i - m] = xx[v] + bb[i]; } merge(xx, vv, k2, vv_, k2_), k2 += k2_; } ans = 0; for (h1 = 0; h1 < k1; h1++) if (ww[uu[h1]] >= l) ans++; for (h2 = 0; h2 < k2; h2++) if (xx[vv[h2]] >= l) ans++; for (h1 = 0, h2 = k2 - 1; h1 < k1; h1++) { u = uu[h1]; while (h2 >= 0 && ww[u] + xx[vv[h2]] >= l) { if (vv[h2] > 0) kk[first[vv[h2]]]++; h2--; } if (u > 0) for (i = m; i < n; i++) if (aa[last[u]] <= aa[i]) ans += kk[i - m]; } printf("%lld\n", ans); return 0; }

Compilation message (stderr)

san.c: In function 'main':
san.c:62:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   62 |     xx[vv_[k2_++] = v | 1 << i - m] = xx[v] + bb[i];
      |                              ~~^~~
san.c:41:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%lld", &n, &l), m = n / 2;
      |  ^~~~~~~~~~~~~~~~~~~~~~~
san.c:43:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d", &aa[i], &bb[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...