제출 #778891

#제출 시각아이디문제언어결과실행 시간메모리
778891magician은행 (IZhO14_bank)C++11
100 / 100
107 ms8524 KiB
#include<iostream>

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

using namespace std;

const int N = 20;

int n, m;
int a[N], b[N];

int f[MASK(N)], g[MASK(N)];

int main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  cin >> n >> m;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for(int i = 0; i < m; i++) {
    cin >> b[i];
  }

  for(int mask = 0; mask < MASK(m); mask++) {
    f[mask] = g[mask] = -1;
  }

  f[0] = 0;
  g[0] = 0;

  for(int mask = 1; mask < MASK(m); mask++) {
    for(int i = 0; i < m; i++) {
      if(!BIT(mask, i)) continue;
      if(f[mask ^ MASK(i)] == -1) continue;
      int new_amt = g[mask ^ MASK(i)] + b[i];
      int tar_amt = a[f[mask ^ MASK(i)]];
      if(new_amt < tar_amt) {
        if(f[mask] <= f[mask ^ MASK(i)]) {
          f[mask] = f[mask ^ MASK(i)];
          g[mask] = new_amt;
        }
      }
      else if(new_amt == tar_amt) {
        if(f[mask] < f[mask ^ MASK(i)] + 1) {
          f[mask] = f[mask ^ MASK(i)] + 1;
          g[mask] = 0;
        }
      }
    }
    if(f[mask] == n) {
      cout << "YES";
      return 0;
    }
  }
  cout << "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...