제출 #1139803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139803		fryingduc	Bank (IZhO14_bank)	C++20	100 / 100	95 ms	8644 KiB

bank

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

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