Submission #944302

#	Time	Username	Problem	Language	Result	Execution time	Memory
944302		4QT0R	Bank (IZhO14_bank)	C++17	71 / 100	1070 ms	6412 KiB

bank

#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++;
	if (koniec>5e7)return false;
	for (auto u : maski[sal[pos]]){
		if (!(u&maska) && backtrack(u^maska,pos+1))return true;
	}
	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";
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29