Submission #1141305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141305		crispxx	Bank (IZhO14_bank)	C++20	100 / 100	102 ms	16712 KiB

bank

/**
 *    author: a.k
 *    created: idk
**/
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define int long long
#define nl '\n'

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m; cin >> n >> m;
	
	vector<int> a(n), b(m);
	for(auto &u : a) cin >> u;
	for(auto &u : b) cin >> u;
	
	vector<int> rem(1 << m, -1), cnt(1 << m, -1);
	rem[0] = 0;
	cnt[0] = 0;
	for(int mask = 0; mask < 1 << m; mask++) {
		for(int last = 0; last < m; last++) {
			if(!(mask >> last & 1)) continue;
			int prev = mask & ~(1 << last);
			if(cnt[prev] == -1) continue;
			
			int cur = rem[prev] + b[last];
			int targ = a[cnt[prev]];
			
			if(cur < targ) {
				cnt[mask] = cnt[prev];
				rem[mask] = cur;
			}
			
			if(cur == targ) {
				cnt[mask] = cnt[prev] + 1;
				rem[mask] = 0;
			}
		}
		if(cnt[mask] == n) {
			cout << "YES" << nl;
			return 0;
		}
	}
	cout << "NO" << nl;
}

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