Submission #1076974

#TimeUsernameProblemLanguageResultExecution timeMemory
1076974xnqsBank (IZhO14_bank)C++17
100 / 100
116 ms10772 KiB
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
#include <functional>

int tgt_cnt, x;
int tgt[25];
int arr[25];
char vis[20][1<<20];

void sol(int pos, int mask) {
	if (pos==tgt_cnt) {
		std::cout << "YES\n";
		exit(0);
	}
	if (vis[pos][mask]) {
		return;
	}
	vis[pos][mask] = 1;

	const std::function<void(int,int,int)> back = [&](int k, int m, int sum) {
		if (sum>tgt[pos]) {
			return;
		}
		if (k==x) {
			if (sum==tgt[pos]) {
				sol(pos+1,mask|m);
			}
			return;
		}

		back(k+1,m,sum);
		if (!((mask>>k)&1)) {
			back(k+1,m|(1<<k),sum+arr[k]);
		}
	};

	back(0,0,0);
}

int main() {
	std::cin >> tgt_cnt >> x;
	for (int i = 0; i < tgt_cnt; i++) {
		std::cin >> tgt[i];
	}
	for (int i = 0; i < x; i++) {
		std::cin >> arr[i];
	}

	std::sort(tgt,tgt+tgt_cnt);

	sol(0,0);
	std::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...