Submission #1369218

#TimeUsernameProblemLanguageResultExecution timeMemory
1369218haught_veathBank (IZhO14_bank)C++20
71 / 100
461 ms327680 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define fastio ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define all(x) x.begin(),x.end()
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);
  }
};
int n,m;
vector<int>sum[20],compress;
int main() {
  cin >> n >> m;
  vector<int> a(n),ac(n),b(m);
  for(int i = 0;i < n;i++){
    cin >> a[i];
    compress.push_back(a[i]);
  }
  for(int j = 0;j < m;j++)cin >> b[j];
  sort(a.rbegin(),a.rend());
  sort(all(compress));
  compress.erase(unique(all(compress)),compress.end());
  for(int i = 0;i < n;i++)ac[i] = lower_bound(all(compress),a[i]) - compress.begin();
  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 j = 0;j < n;j++){
      if(tong == a[j]){
        sum[ac[j]].push_back(i);
        break;
      }
    }
  }
  queue<pair<int,int>> q;
  q.push({0,0});
  while(!q.empty()){
    auto [id,mask] = q.front();
    if(id == n){
      cout << "YES\n";
      return 0;
    }
    q.pop();
    for(int sub : sum[ac[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...