Submission #1076967

#TimeUsernameProblemLanguageResultExecution timeMemory
1076967xnqsBank (IZhO14_bank)C++17
71 / 100
1068 ms21080 KiB
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

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

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

	for (int mask2 = 0; mask2 < (1<<x); mask2++) {
		if (mask2&mask) {
			continue;
		}

		int sum = 0;
		for (int i = 0; i < x; i++) {
			if (mask2&(1<<i)) {
				sum += arr[i];
			}
			if (sum>tgt[pos]) {
				goto gtfo;
			}
		}

		if (sum==tgt[pos]) {
			sol(pos+1,mask|mask2);
		}

gtfo:
		continue;
	}

	return (void)(dp[pos][mask] = 1);
}

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];
	}

	memset(dp,-1,sizeof(dp));
	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...