제출 #380529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380529		MilosMilutinovic	은행 (IZhO14_bank)	C++14	100 / 100	414 ms	10604 KiB

bank

/**
 *    author:  milos
 *    created: 22.03.2021 08:41:57       
**/
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  vector<int> b(m);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) cin >> b[i];
  const int MAX = 2e4 + 5;
  vector<vector<int>> v(MAX);
  for (int i = 0; i < (1 << m); i++) {
    int sum = 0;
    for (int j = 0; j < m; j++) {
      if (i & (1 << j)) {
        sum += b[j];
      }                   
    }
    v[sum].push_back(i);
  }                           
  vector<int> masks;
  masks.push_back(0);
  vector<vector<bool>> was(n, vector<bool>((1 << m), false));
  for (int i = 0; i < n; i++) {
    vector<int> nm;           
    for (int j : v[a[i]]) {
      for (int k : masks) {
        if ((j ^ k) == (j | k) && !was[i][j ^ k]) {
          nm.push_back(j ^ k);
          was[i][j ^ k] = true; 
        }
      }
    }
    swap(nm, masks);
  }     
  cout << (masks.empty() ? "NO" : "YES") << '\n';
  return 0;
}

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