Submission #656378

#	Time	Username	Problem	Language	Result	Execution time	Memory
656378		boykut	Bank (IZhO14_bank)	C++14	44 / 100	1086 ms	4224 KiB

bank

#include <iostream>

using namespace std;

const int N = 22;
int a[N], b[N], dp[N][1<<N], n, m;

int Sum(int mask) {
	int s = 0;
	for (int i = 0; i < m; i++) {
		if ((mask>>i)%2 == 1) s += b[i];
	}
	return s;
}

int main() {
	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++) {
		if (Sum(mask) == a[0]) dp[0][mask] = 1;
	} // 2^m * m
	for (int i = 1; i < n; i++) {
		for (int mask = 0; mask < (1<<m); mask++) {
			if (Sum(mask) < a[i]) continue;
			for (int p = 0; p < (1<<m); p++) {
				if (Sum(p) == a[i]) {
					int False = 0;
					for (int j = 0; j < m; j++) {
						if ((mask>>j)%2 == 0 && (p>>j)%2 == 1) {
							False = 1;
							break;
						}
					}
					if (False == 0) {
						if (dp[i - 1][mask ^ p] == 1)
							dp[i][mask] = 1;
					}
				}
			}
		}
	}
	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: 0 / 27
• Subtask 4: 0 / 29