제출 #1286143

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286143		OmarAlimammadzade	Bank (IZhO14_bank)	C++20	52 / 100	1096 ms	10684 KiB

bank

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

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