Submission #173746

#TimeUsernameProblemLanguageResultExecution timeMemory
173746touristBank (IZhO14_bank)C++14
100 / 100
259 ms16496 KiB
#include <iostream>
#include <time.h>
#include <vector>

using namespace std;

#define ll long long
#define sz(x) (int)x.size()
#define pii pair < int, int >
#define endl "\n"
#define METH ios::sync_with_stdio(0); cin.tie(0);
#define BEGIN cout << "BEGIN" << endl;
#define END cout << "END" << endl;

const int mod = 1e9 + 7;															/// ANOTHER HASH MOD: 228228227
const int prime = 29;																	/// ANOTHER HASH PRIME: 997
const int INF = ((long long) 0xCAFEBABE - 1e9 - 4e8);

int n, m;
short pre[1 << 20];
bool dp[21][1 << 20];
vector < short > a, b;
vector < int > trans[20];

inline void read() {
	cin >> n >> m;
	a.resize(n + 1);
	b.resize(m + 1);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
}

void calc(int mask, int cnt) {
	if (cnt == n) {
		cout << "YES" << endl;
		exit(0);
	}
	if (dp[cnt][mask]) {
		return;
	}
	dp[cnt][mask] = 1;
	for (int sub : trans[cnt]) {
		if ((mask & sub) == sub) {
			calc(mask ^ sub, cnt + 1);
		}
	}
}

inline int solve() {
	for (int i = 0; i < (1 << m); i++) {
		int sum = 0;
		for (int j = 0; j < m; j++) {
			if (i >> j & 1) {
				sum += b[j];
			}
		}
		pre[i] = sum;
		for (int j = 0; j < n; j++) {
			if (pre[i] == a[j]) {
				trans[j].push_back(i);
			}
		}
	}
	calc((1 << m) - 1, 0);
	cout << "NO" << endl;
	return 0;
}

int main() {
	METH
	int t = 1;
	while (t--) {
		read();
		solve();
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...