Submission #173746

#	Time	Username	Problem	Language	Result	Execution time	Memory
173746		tourist	Bank (IZhO14_bank)	C++14	100 / 100	259 ms	16496 KiB

bank

#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();
	}
}

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