Submission #212942

#	Time	Username	Problem	Language	Result	Execution time	Memory
212942		islingr	Bank (IZhO14_bank)	C++14	100 / 100	276 ms	82456 KiB

bank

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define per(i, a, b) for (auto i = (b) - 1; i >= (a); --i)
#define trav(x, v) for (auto &x : v)
#define ff first
#define ss second

using ll = int64_t;

template<class T> bool ckmin(T &a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T &a, const T& b) { return a < b ? a = b, 1 : 0; }

const int N = 20;
int n, m, a[N], b[N];
vector<int> r[N];
int f[N][1 << N];

bool solve(int S, int i) {
	if (i == 0) return true;
	if (S == 0) return false;
	--i;
	auto &h = f[i][S];
	if (h != -1) return h;
	trav(x, r[i])
		if ((x & S) == x)
			if (solve(S & ~x, i))
			return h = true;
	return h = false;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	rep(i, 0, n) cin >> a[i];
	rep(i, 0, m) cin >> b[i];
	rep(S, 0, 1 << m) {
		int sum = 0;
		rep(j, 0, m) if (S & 1 << j) sum += b[j];
		rep(i, 0, n) if (sum == a[i]) r[i].emplace_back(S);
	}
	rep(S, 0, 1 << m) rep(i, 0, n) f[i][S] = -1;
	cout << (solve((1 << m) - 1, n) ? "YES" : "NO");
}

Compilation message (stderr)

bank.cpp: In function 'bool solve(int, int)':
bank.cpp:31:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    return h = true;
           ~~^~~~~~
bank.cpp:32:11: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return h = false;
         ~~^~~~~~~

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