제출 #1067489

#제출 시각아이디문제언어결과실행 시간메모리
1067489horezushol은행 (IZhO14_bank)C++14
19 / 100
75 ms8580 KiB
#include<bits/stdc++.h>
#define F first
#define S second
#define SZ(x) int((x).size())
const char nl = '\n';
using namespace std;

int sum[(1 << 20)];
vector<int> v[1010];
int a[20], b[20];
int n, m;


bool dp[20][(1 << 20)];
// dp[i][mask] = true, if [0; i] can be payed with #mask of B


void verkefni() {
	cin >> n >> m;
	for (int i = 0; i < n; i ++) cin >> a[i];
	for (int i = 0; i < m; i ++) cin >> b[i];
	for (int mask = 0; mask < (1 << m); mask ++) {
		for (int i = 0; i < m; i ++) {
			if (mask & (1 << i)) sum[mask] += b[i];
		}
	}
	for (int i = 0; i < n; i ++) {
		for (int mask = 0; mask < (1 << m); mask ++) {
			if (sum[mask] == a[i]) {
				v[a[i]].push_back(mask);
			}
		}
	}
	for (auto el : v[a[0]]) {
		dp[0][el] = true;
	}
	for (int mask = 0; mask < (1 << m); mask ++) {
		if (dp[0][mask]) {
			for (int i = 0; i < m; i ++) {
				if (mask != (mask | (1 << i))) {
					// cout << mask << " " << (mask | (1 << i)) << nl;
				}
				dp[0][mask | (1 << i)] = true;
			}
		}
	}
	int tot = 0;
	for (int i = 0; i < n; i ++) {
		for (int mask = 0; mask < (1 << m); mask ++) {
			if (i > 0) {
				if (!dp[i-1][mask]) continue;
			} else {
				if (!dp[i][mask]) continue;
			}
			if (sum[mask] - tot == a[i]) {
				dp[i][mask] = true;
				for (int j = 0; j < m; j ++) {
					dp[i][mask | (1 << j)] = true;
				}
			}
		}
		tot += a[i];
	}
	// cout << "\n-----------------\n";
	if (dp[n-1][(1 << m)-1]) {
		cout << "YES";
	} else {
		cout << "NO";
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tst = 1;
	// cin >> tst;
	while (tst --) {
		verkefni();
		cout << nl;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...