Submission #656382

#	Time	Username	Problem	Language	Result	Execution time	Memory
656382		boykut	Bank (IZhO14_bank)	C++17	71 / 100	1096 ms	10116 KiB

bank

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int N = 22;
int a[N], b[N], dp[N][1<<N], n, m;
vector<int> can[1001];
 
int main() {
	cin.tie()->sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	int mx = *max_element(a, a+n);
	for (int mask = 0; mask < (1<<m); mask++) {
		int s = 0;
		for (int i = 0; i < m; i++) {
			if (((mask>>i)&1)) s += b[i];
		}
		if (s <= mx)
			can[s].push_back(mask);
	}
 
	for (int mask : can[a[0]])
		dp[0][mask] = 1;
 
	for (int i = 1; i < n; i++) {
		for (int mask = 0; mask < (1<<m); mask++) {
			for (int p : can[a[i]]) {
				if ((mask & p) == p) {
					dp[i][mask] |= dp[i-1][mask^p];
				}
			}
		}
	}
	for (int mask = 0; mask < (1<<m); mask++) {
		if (dp[n-1][mask] == 1)
			return cout << "YES", 0;
	}
	return cout << "NO", 0;
}

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