Submission #1369236

#TimeUsernameProblemLanguageResultExecution timeMemory
1369236haught_veathBank (IZhO14_bank)C++20
100 / 100
259 ms16944 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;
bool vis[21][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 = 0;i < (1<<m);i++){
    int tong = 0;
    for(int j = 0;j < m;j++)
      if((1LL<<j)&i)tong += b[j];
    for(int x : a){
      if(tong == x){
        sum[tong].push_back(i);
        break;
      }
    }
  }
  queue<pair<int,int>> q;
  q.push({0,0});
  vis[0][0] = 1;
  while(!q.empty()){
    auto [id,mask] = q.front();
    if(id == n){
      cout << "YES\n";
      return 0;
    }
    q.pop();
    for(int sub : sum[a[id]]){
      if(mask&sub || vis[id+1][mask|sub])continue;
      q.push({id+1,mask|sub});
      vis[id+1][mask|sub] = 1;
    }
  }
  cout << "NO\n";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...