제출 #1369198

#제출 시각아이디문제언어결과실행 시간메모리
1369198haught_veath은행 (IZhO14_bank)C++20
71 / 100
422 ms327680 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define rall(x) x.begin(),x.end()
#define fastio ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
using namespace __gnu_pbds;
using namespace std;
const int maxn = (1<<20)+1;
const int rd = chrono::steady_clock::now().time_since_epoch().count();
struct chash{
  size_t split(size_t x)const {
    x += 0x9e3779b97f4a7c15ULL;
    x = (x^(x>>31))*0xbf57486d1ce4e5b9ULL;
    x = (x^(x>>27))*0x94d049bb133111ebULL;
    return (x^(x>>30));
  }
  size_t operator() (size_t x)const{
    return split(x + rd);
  }
};
gp_hash_table<int,vector<int>,chash> sum;
int n,m,dp[maxn];
int main() {
  cin >> n >> m;
  vector<int> a(n),b(m);
  for(int i = 0;i < n;i++)cin >> a[i];
  for(int j = 0;j < m;j++)cin >> b[j];
  sort(a.rbegin(),a.rend());
  for(int i = 1;i < (1<<m);i++){
    int bit = __lg(i);
    dp[i] = dp[(i^(1LL<<bit))] + b[bit];
    sum[dp[i]].push_back(i);
  }
  queue<pair<int,int>> q;
  q.push({0,0});
  while(!q.empty()){
    auto [mask,id] = q.front();
    if(id == n){
      cout << "YES\n";
      exit(0);
    }
    q.pop();
    for(int sub : sum[a[id]]){
      if(mask&sub)continue;
      q.push({mask|sub,id+1});
    }
  }
  cout << "NO\n";
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…