Submission #1071905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071905		horezushol	Bank (IZhO14_bank)	C++14	71 / 100	1052 ms	12636 KiB

bank

#include<bits/stdc++.h>
#define F first
#define S second
#define SZ(x) int((x).size())
const char nl = '\n';
using ll = long long;
using namespace std;

const int N = 20;
bool dp[N][(1 << N)];
int sum[(1 << N)];

int n, m;
int a[N], b[N];


void verkefni() {
	cin >> n >> m;
	for (int i = 0; i < n; i ++) cin >> a[i];
	for (int j = 0; j < m; j ++) cin >> b[j];
	for (int mask = 0; mask < (1 << m); mask ++) {
		int cur = 0;
		for (int i = 0; i < m; i ++) {
			if (mask & (1 << i)) {
				cur += b[i];
			}
		}
		sum[mask] = cur;
	}
	for (int mask = 0; mask < (1 << m); mask ++) { // i = 0
		if (sum[mask] == a[0]) {
			dp[0][mask] = true;
		}
	}
	for (int i = 0; i < n-1; i ++) {
		for (int mask = 0; mask < (1 << m); mask ++) {
			if (!dp[i][mask]) continue; // The actual solution is O(2^M * 2^M * N), but because of that IF, it becomes O(2^M * N * M) (cause there's M [dp[i][mask] == true] at most)
			for (int cur = 0; cur < (1 << m); cur ++) {
				if (mask <= cur && (mask & cur) == mask) {
					if (sum[cur] - sum[mask] == a[i+1]) {
						// cout << sum[cur] << " " << sum[mask] << " " << b[i+1] << nl;
						dp[i+1][cur] = true;
					}
				}
			}
		}
	}
	// cout << nl;
	for (int mask = 0; mask < (1 << m); mask ++) {
		if (dp[n-1][mask]) {
			cout << "YES";
			return ;
		}
	}
	cout << "NO";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tst = 1;
	// cin >> tst;
	while (tst --) {
		verkefni();
		cout << nl;
	}
}

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