Submission #1194204

#TimeUsernameProblemLanguageResultExecution timeMemory
1194204PlayVoltzBank (IZhO14_bank)C++20
71 / 100
1095 ms728 KiB
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std; 

int n, m;
vector <int> ppl;
vector <int> notes;
unordered_map<int, bool> exist;
unordered_map<int, vector<int> > masks;

bool can(int index, int mask){
	if (index==n-1){
		return true;
	}
	for (auto num:masks[ppl[index+1]]){
		if ((mask&num)==0){
			if (can(index+1, mask+num))return true;
		}
	}
	return false;
}

int main(){
  ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	ppl.resize(n);
	notes.resize(m);
	for (int i=0; i<n; ++i){
		cin>>ppl[i];
		exist[ppl[i]] = true;
	}
	for (int i=0; i<m; ++i){
		cin>>notes[i];
	}
	for (int i=0; i<(1ll<<m); ++i){
		int sum = 0;
		for (int j=0; j<=m; ++j){
			if (i&(1ll<<j)){
				sum+=notes[j];
			}
		}
		if (exist[sum]){
			masks[sum].push_back(i);
		}
	}
	if (can(-1, 0))cout<<"YES";
	else cout<<"NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...