제출 #778891

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

bank

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

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