Submission #499095

#	Time	Username	Problem	Language	Result	Execution time	Memory
499095		boykut	Bank (IZhO14_bank)	C++14	100 / 100	449 ms	86592 KiB

bank

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	srand(time(NULL));

	int n, m;
	cin >> n >> m;

	vector<int> a(n), b(m);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < m; i++) cin >> b[i];

	vector<vector<int>> can(*max_element(begin(a), end(a)) + 1);
	for (int mask = 0; mask < (1 << m); mask++) {
		int s = 0;
		for (int i = 0; i < m; i++)
			if (mask & (1 << i)) s += b[i];
		if (s < can.size())
			can[s].push_back(mask);
	}

	vector<vector<int>> dp(n, vector<int>(1 << m, 0));
	for (int x : can[a[0]])
		dp[0][x] = 1;
	for (int i = 1; i < n; i++) {
		for (int mask = 0; mask < (1 << m); mask++) {
			if (dp[i - 1][mask] == 0) continue;
			for (auto x : can[a[i]]) {
				if ((mask & x) != 0) continue;
				dp[i][mask | x] = 1;
			}
		}
	}

	bool ok = false;
	for (int mask = 0; mask < (1 << m); mask++)
		ok |= dp[n - 1][mask] == 1;

	if (ok) cout << "YES\n";
	else cout << "NO\n";

	return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:22:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   if (s < can.size())
      |       ~~^~~~~~~~~~~~

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