Submission #944307

#TimeUsernameProblemLanguageResultExecution timeMemory
9443074QT0RBank (IZhO14_bank)C++17
71 / 100
374 ms6444 KiB
#include <bits/stdc++.h>
using namespace std;

int sal[22];
int val[22];
vector<int> maski[1002];
int n,m,koniec=0;

bool backtrack(int maska, int pos){
	if (pos==n)return true;
	koniec++;
	for (auto u : maski[sal[pos]]){
		if (!(u&maska) && backtrack(u^maska,pos+1))return true;
		if (koniec>1000000)return false;
	}
	return false;
}

bool sorting(int a, int b){
	return maski[a].size()<maski[b].size();
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int v;
	cin >> n >> m;
	multiset<int> wart,bank;
	for (int i = 0; i<n; i++){
		cin >> v;
		wart.insert(v);
	}
	for (int i = 0; i<m; i++){
		cin >> v;
		auto it=wart.find(v);
		if (it!=wart.end())wart.erase(it);
		else bank.insert(v);
	}
	n=wart.size();
	m=bank.size();
	if (n>10){
		cout << "NO\n";
		return 0;
	}
	int iter=0,sm;
	for (auto u : wart)sal[iter++]=u;
	iter=0;
	for (auto u : bank)val[iter++]=u;
	for (int i = 1; i<(1<<m); i++){
		sm=0;
		for (int j = 0; j<m; j++){
			if (i&(1<<j))sm+=val[j];
		}
		if (sm<=1000)maski[sm].push_back(i);
	}
	sort(sal,sal+n,sorting);
	if (backtrack(0,0))cout << "YES\n";
	else cout << "NO\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...