Submission #254985

#	Time	Username	Problem	Language	Result	Execution time	Memory
254985		penguinhacker	Bank (IZhO14_bank)	C++17	100 / 100	94 ms	8696 KiB

bank

//Day 1 Problem B: bank
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

int n, m, a[20], b[20];
pair<int, int> dp[1<<20]; // <i, j> = <done with first i people, payed (i+1)th person j>
bool pos=0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i=0; i<n; ++i) cin >> a[i];
	for (int i=0; i<m; ++i) cin >> b[i];
	for (int i=1; i<(1<<m); ++i) dp[i].first=-1;
	for (int mask=0; mask<(1<<m); ++mask) {
		if (dp[mask]==make_pair(n, 0)) {
			pos=1;
			break;
		}
		if (dp[mask].first==-1) continue;
		int ind=dp[mask].first, payed=dp[mask].second; //index of person we are on (0-indexed), amount we have already payed
		assert(ind<n&&payed<a[ind]);
		for (int i=0; i<m; ++i) if (!(mask&(1<<i))) {
			if (payed+b[i]>a[ind]) continue;
			if (payed+b[i]==a[ind]) dp[mask|(1<<i)]={ind+1, 0};
			else dp[mask|(1<<i)]={ind, payed+b[i]};
		}
	}
	cout << (pos?"YES":"NO");
	return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/

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