Submission #1346103

#TimeUsernameProblemLanguageResultExecution timeMemory
1346103jumpBank (IZhO14_bank)C++20
71 / 100
1094 ms652 KiB
#include <bits/stdc++.h>
#define int long long
int n,m;
int dp[1<<20];
int narr[21];
int barr[21];
std::vector<int> corrbit[21];
bool bitcheck(int bit1,int bit2){
	return (bit1&bit2)==0;
}
bool dfs(int i,int bit){
	for(int com:corrbit[i]){
		if(bitcheck(com,bit)){
			if(i>=n-1)return true;
			if(dfs(i+1,com|bit))return true;
		}
	}
	return false;
}
bool check(int total,int bit){
	int sum=0;
	for(int i=0;i<m;i++){
		if(((1<<i)&bit)!=0){
			sum+=barr[i];
		}
	}
	//std::cout << ' ' << sum << '\n';
	return sum==total;
}
signed main() {
	std::cin >> n >> m;
	for(int i=0;i<n;i++)std::cin >> narr[i];
	for(int i=0;i<m;i++)std::cin >> barr[i];
	for(int i=0;i<n;i++){
		for(int j=0;j<(1<<m);j++){
			//std::cout << j;
			if(check(narr[i],j)){
				corrbit[i].push_back(j);
			}
		}
		// for(auto b:corrbit[i]){
		// 	std::cout << b << ' ';
		// }std::cout << '\n';
	}
	if(dfs(0,0)){
		std::cout << "YES";
	}else{
		std::cout << "NO";
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...