제출 #650482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
650482		alvinpiter	은행 (IZhO14_bank)	C++17	71 / 100	1095 ms	94672 KiB

bank

#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;
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29