Submission #1062062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062062		horezushol	Bank (IZhO14_bank)	C++14	19 / 100	80 ms	10440 KiB

bank

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

const ll N = 20;
const ll NA = 1010;
ll sum[(1 << N)];
vector<ll> v[NA];
ll a[NA], b[NA];
ll n, m;


bool dp[NA][(1 << N)];


void verkefni() {
	cin >> n >> m;
	for (ll i = 0; i < n; i ++) cin >> a[i];
	for (ll i = 0; i < m; i ++) cin >> b[i];
	for (ll mask = 0; mask < (1 << m); mask ++) {
		for (ll i = 0; i < m; i ++) {
			if (mask & (1 << i)) sum[mask] += b[i];
		}
	}
	for (ll i = 0; i < n; i ++) {
		for (ll mask = 0; mask < (1 << m); mask ++) {
			if (sum[mask] == a[i]) {
				v[a[i]].push_back(mask);
			}
		}
	}
	for (auto el : v[a[0]]) {
		dp[0][el] = true;
	}
	for (ll mask = 0; mask < (1 << m); mask ++) {
		if (dp[0][mask]) {
			for (ll i = 0; i < m; i ++) {
				// cout << mask << " " << (mask | (1 << i)) << nl;
				dp[0][mask | (1 << i)] = true;
			}
		}
	}
	ll tot = a[0];
	for (ll i = 1; i < n; i ++) {
		for (ll mask = 0; mask < (1 << m); mask ++) {
			if (!dp[i-1][mask]) continue;
			if (sum[mask] - tot == a[i]) {
				dp[i][mask] = true;
				for (ll j = 0; j < m; j ++) {
					dp[i][mask | (1 << j)] = true;
				}
			}
		}
		tot += a[i];
	}
	for (ll mask = 0; mask < (1 << m); mask ++) {
		if (dp[n-1][mask]) {
			cout << "YES";
			return ;
		}
	}
	cout << "NO";
	// for (ll i = 0; i < n; i ++) {
		// cout << a[i] << ": ";
		// for (auto el : v[a[i]]) {
			// cout << el << " ";
		// }
		// cout << nl;
	// }
}

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

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