제출 #956327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
956327		Trisanu_Das	은행 (IZhO14_bank)	C++17	100 / 100	105 ms	8792 KiB

bank

#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n, m; cin >> n >> m;
  int a[n], b[m];
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < m; i++) cin >> b[i];
  vector<int> cover(1 << m, -1), left(1 << m, -1);
  left[0] = cover[0] = 0;
  for(int mask = 1; mask < (1 << m); mask++){
    for(int last = 0; last < m; last++){
      if(!(mask & (1 << last))) continue;
      int p = mask & ~(1 << last);
      if(cover[p] == -1) continue;
      int new_ = left[p] + b[last], target = a[cover[p]];
      if(new_ < target){
        cover[mask] = cover[p];
        left[mask] = new_;
      }else if(new_ == target){
        cover[mask] = cover[p] + 1;
        left[mask] = 0;
      }
    }
    if(cover[mask] == n){
      cout << "YES\n"; return 0;
    }
  }
  cout << "NO\n";
}

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