제출 #1286143

#제출 시각아이디문제언어결과실행 시간메모리
1286143OmarAlimammadzade은행 (IZhO14_bank)C++20
52 / 100
1096 ms10684 KiB
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "algo/debug"
#else
#define dbg(...)
#endif

#define int long long

void run() {
  int n, m;
  cin >> n >> m;
  int a[n + 1], b[m + 1];
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
  }
  int sum[1 << m];
  fill(sum, sum + (1 << m), 0);
  for (int msk = 0; msk < 1 << m; msk++) {
    for (int i = 0; i < m; i++) {
      sum[msk] += (msk >> i & 1) * b[i + 1];
    }
  }
  bool dp[n + 1][1 << m];
  fill(&dp[0][0], &dp[0][0] + (n + 1) * (1 << m), false);
  dp[0][0] = true;
  for (int i = 1; i <= n; i++) {
    for (int msk = 0; msk < 1 << m; msk++) {
      for (int sub = msk; sub; sub = (sub - 1) & msk) {
        if (sum[sub] == a[i]) {
          dp[i][msk] |= dp[i - 1][msk ^ sub];
        }
      }
    }
  }
  for (int msk = 0; msk < 1 << m; msk++) {
    if (dp[n][msk]) {
      cout << "YES\n";
      return;
    }
  }
  cout << "NO\n";
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  int tt = 1;
  // cin >> tt;
  while (tt--) {
    run();
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...