Submission #1369202

#TimeUsernameProblemLanguageResultExecution timeMemory
1369202haught_veathBank (IZhO14_bank)C++20
71 / 100
1102 ms268232 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;
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];
    sum[tong].push_back(i);
  }
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
  // p_queue<pair<int,int>> q;
  q.push({0,0});
  while(!q.empty()){
    auto [id,mask] = q.top();
    if(id == n){
      cout << "YES\n";
      exit(0);
    }
    q.pop();
    for(int sub : sum[a[id]]){
      if(mask&sub)continue;
      q.push({id+1,mask|sub});
    }
  }
  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...