Submission #1319231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319231		tkm_algorithms	Bank (IZhO14_bank)	C++20	100 / 100	322 ms	11200 KiB

bank

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
//#define int ll
using P = pair<int, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const int mod = 1e9+7;
const int N = 20;

int sum[1<<N], vis[1<<N];

void solve() {
	int n, m; cin >> n >> m;
	vector<int> a(n), b(m);
	for (auto &i: a)cin >> i;
	for (auto &i: b)cin >> i;
	
	rep(i, 1, (1<<m))
		rep(j, 0, m)
			if (i&(1<<j))sum[i] += b[j];
	
	vector<int> g[n];
	rep(i, 0, n)
		rep(j, 1, (1<<m))
			if (sum[j] == a[i])g[i].push_back(j);

	vector<int> l = g[0];
	
	rep(i, 1, n) {
		vector<int> nw;
		for (auto j: l)
			for (auto k: g[i])if (!(k&j) && !vis[k|j])nw.push_back(k|j), vis[k|j] = 1;
		l = nw;
		memset(vis, 0, sizeof vis);
	}
	
	cout << (sz(l)?"YES":"NO") << nl;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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