제출 #650482

#제출 시각아이디문제언어결과실행 시간메모리
650482alvinpiter은행 (IZhO14_bank)C++17
71 / 100
1095 ms94672 KiB
#include<bits/stdc++.h>
using namespace std;

int n, m, a[22], b[22], sum[(1 << 20) + 3];
int dp[22][(1 << 20) + 2];

int solve(int j, int mask) {
  if (j == -1) {
    return 1;
  }

  if (dp[j][mask] != -1) {
    return dp[j][mask];
  }

  dp[j][mask] = 0;
  for (int submask = mask; submask > 0; submask = (submask - 1)&mask) {
    if (sum[submask] == a[j] && solve(j - 1, mask^submask) == 1) {
      dp[j][mask] = 1;
    }
  }

  return dp[j][mask];
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }

  for (int mask = 0; mask < (1 << m); mask++) {
    sum[mask] = 0;
    for (int i = 0; i < m; i++) {
      if (mask & (1 << i)) {
        sum[mask] += b[i];
      }
    }
  }

  memset(dp, -1, sizeof(dp));

  cout << (solve(n - 1, (1 << m) - 1) == 1 ? "YES" : "NO") << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...