Submission #1369231

#TimeUsernameProblemLanguageResultExecution timeMemory
1369231haught_veath은행 (IZhO14_bank)C++20
71 / 100
1095 ms9024 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,sum[maxn];
bool vis[21][maxn];
int main() {
  cin >> n >> m;
  vector<int> a(n),ac(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);
    sum[i] = sum[(i^(1LL<<bit))] + b[bit];
  }
  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();
    int rem = (((1LL<<m)-1)^mask);
    for(int sub = rem;true;sub = (sub-1)&rem){
      if(sub == 0)break;
      if(sum[sub] != a[id] || vis[id+1][sub|mask])continue;
      vis[id+1][mask|sub] = 1;
      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...