Submission #1139803

#TimeUsernameProblemLanguageResultExecution timeMemory
1139803fryingducBank (IZhO14_bank)C++20
100 / 100
95 ms8644 KiB
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int W = 1005;
const int MASK = (1 << 20) + 5;
int n, m, a[25], b[25];
int f[MASK], rem[MASK];

void solve() {
  cin >> n >> m;
  if(n > m) {
    cout << "NO";
    return;
  }
  for(int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for(int i = 1; i <= m; ++i) {
    cin >> b[i];
  }
  memset(f, -1, sizeof(f));
  memset(rem, -1, sizeof(rem));
  f[0] = rem[0] = 0;
  for(int mask = 0; mask < (1 << m); ++mask) { 
    for(int i = 0; i < m; ++i) {
      if((mask >> i & 1) == 0) continue;
      int prv = mask ^ (1 << i);
      if(f[prv] == -1) continue;
      
      int x = rem[prv] + b[i + 1];
      if(x < a[f[prv] + 1]) {
        f[mask] = f[prv];
        rem[mask] = x;
      } else if(x == a[f[prv] + 1]) {
        f[mask] = f[prv] + 1;
        rem[mask] = 0;
      }
    }
  }
  for(int mask = 0; mask < (1 << m); ++mask) {
    if(f[mask] == n) {
      cout << "YES";
      return;
    }
  }
  cout << "NO";
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}


#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...