Submission #573450

#TimeUsernameProblemLanguageResultExecution timeMemory
573450_karan_gandhiBank (IZhO14_bank)C++17
100 / 100
113 ms8540 KiB
#include <bits/stdc++.h>
using namespace std;

#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long

void solve() {
	// covered[mask] = max prefix of people that we can pay
	// leftover[mask] = amount of money left over after we pay off the people
	int n, m; cin >> n >> m;

	vector<int> covered(1 << m, 0), leftover(1 << m, 0);
	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];
	}

	for (int subset = 1; subset < (1 << m); subset++) {
		for (int bit = 0; bit < m; bit++) {
			if (subset & (1 << bit)) {
				int prev = subset ^ (1 << bit);

				int next = covered[prev];
				int left = leftover[prev];
				if (next == n) continue;

				if (a[next] == left + b[bit]) {
					covered[subset] = max(covered[subset], next + 1);
					if (covered[subset] == next + 1) {
						leftover[subset] = 0;
					}
				} else {
					covered[subset] = max(covered[subset], next);
					if (covered[subset] == next) leftover[subset] = left + b[bit];
				}
			}
		}
	}

	for (int subset = 1; subset < (1 << m); subset++) {
		if (covered[subset] == n) {
			cout << "YES" << endl;
			return;
		}
	}

	cout << "NO" << endl;
}

int main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	// cin >> T;
	while (T--)
		solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...