제출 #1348955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1348955		cpismayilmmdv985	Bank (IZhO14_bank)	C++20	큐에 대기중	0 ms	0 KiB

bank

#ifdef LOCAL
#include ".debug.hpp"
#else
#define debug(...) 42
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

const int MXN = 1 << 21;
int N, M, A[20], B[20];
vector<int> sum[MXN];
map<array<int, 2>, bool> memo;

bool dfs(const int &mask_salary, const int &mask_money) {
   if (!mask_salary) return true;
   if (memo.count({mask_salary, mask_money})) return memo[{mask_salary, mask_money}];
   for (int i = 0; i < N; i++) 
      if (mask_salary & (1 << i)) 
         for (auto &s : sum[A[i]])  if ((s & mask_money) == s) {
            if (dfs(mask_salary ^ (1 << i), mask_money ^ s)) return memo[{mask_salary, mask_money}] = true;
            else  memo[{mask_salary ^ (1 << i), mask_money ^ s}] = false;
         }
   return memo[{mask_salary, mask_money}] = false;
}

signed main() {
#ifndef VOID
   cin.tie(nullptr)->sync_with_stdio(false);
#endif
   
   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 = 1; mask < (1 << M); mask++) {
      int total = 0;
      for (int i = 0; i < M; i++)   if (mask & (1 << i))    total += B[i];
      sum[total].push_back(mask);
   }
   cout << (dfs((1 << N) - 1, (1 << M) - 1) ? "YES" : "NO");

   return 0;
}