제출 #944288

#제출 시각아이디문제언어결과실행 시간메모리
9442884QT0R은행 (IZhO14_bank)C++17
71 / 100
1064 ms6768 KiB
#include <bits/stdc++.h>
using namespace std;

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

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

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);
	}
	if (backtrack(0,n-1))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...