제출 #1348954

#제출 시각아이디문제언어결과실행 시간메모리
1348954cpismayilmmdv985은행 (IZhO14_bank)C++20
71 / 100
1095 ms22316 KiB
#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) {
      memo[{mask_salary, mask_money}] = true;
      cout << "YES\n";
      exit(0);
   }
   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;
   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);
   }
   // dfs((1 << N) - 1, (1 << M) - 1);
   // cout << "NO";
   cout << (dfs((1 << N) - 1, (1 << M) - 1) ? "YES" : "NO");

   return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...