Solution to Sharing Chocolage from WF10 Problem J

J.cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <numeric>

using namespace std;

typedef unsigned int u4;

#define MAXN 15
#define MAXF 100
#define BITS (1 + MAXF / 32)

int A[MAXN];
int S[1 << MAXN];
u4 CANBIT[1 << MAXN][BITS];

int main() {
  int N;
  for(int t = 1; (cin >> N) && N; t++) {
    int R, C;
    cin >> R >> C;
    for(int i = 0; i < N; i++) {
      cin >> A[i];
    }
    if(accumulate(A, A + N, 0) != R * C) {
      printf("Case %d: No\n", t);
      continue;
    }

    memset(CANBIT, 0, sizeof(CANBIT));
    for(int m = 1; m < 1 << N; m++) {
      int bt = __builtin_ctz(m);
      S[m] = S[m ^ 1 << bt] + A[bt];

      if (__builtin_popcount(m) == 1) {
        for(int f = 1; f <= MAXF; f++) {
          if(S[m] % f == 0) {
            CANBIT[m][f >> 5] |= 1U << (f & 0x1F);
          }
        }
        continue;
      }

      for(int s = m - 1 & m; (s ^ m) < s; s = s - 1 & m) {
        int t = s ^ m;
        for(int i = 0; i < BITS; i++) {
          CANBIT[m][i] |= CANBIT[s][i] & CANBIT[t][i];
        }
      }
      for(int f = 1; f <= MAXF; f++) {
        int invf = S[m] / f;
        if(invf * f == S[m] && invf <= MAXF &&
           (CANBIT[m][invf >> 5] & 1U << (invf & 0x1F))) {
          CANBIT[m][f >> 5] |= 1U << (f & 0x1F);
        }
      }
    }

    printf("Case %d: %s\n", t,
           CANBIT[(1 << N) - 1][R >> 5] & 1 << (R & 0x1F) ? "Yes" : "No");
  }
  return 0;
}