Submission #1286182

#TimeUsernameProblemLanguageResultExecution timeMemory
1286182OmarAlimammadzadeBank (IZhO14_bank)C++20
100 / 100
101 ms16848 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], b[m];
  for (int &i : a) {
    cin >> i;
  }
  for (int &i : b) {
    cin >> i;
  }
  int extra[1 << m], dp[1 << m];
  fill(extra, extra + (1 << m), -1);
  fill(dp, dp + (1 << m), -1);
  dp[0] = extra[0] = 0;
  for (int msk = 0; msk < 1 << m; msk++) {
    for (int i = 0; i < m; i++) {
      if (!(msk >> i & 1)) {
        continue;
      }
      int prev = 1 << i ^ msk;
      if (dp[prev] == -1) {
        continue;
      }
      if (extra[prev] + b[i] < a[dp[prev]]) {
        extra[msk] = extra[prev] + b[i];
        dp[msk] = dp[prev];
      } else if (extra[prev] + b[i] == a[dp[prev]]) {
        extra[msk] = 0;
        dp[msk] = dp[prev] + 1;
      }
    }
    if (dp[msk] == n) {
      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...