Submission #573448

#	Time	Username	Problem	Language	Result	Execution time	Memory
573448		_karan_gandhi	Bank (IZhO14_bank)	C++17	19 / 100	68 ms	8532 KiB

bank

#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 {
					leftover[subset] += 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();
}

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