Submission #1131245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131245		catsarecool5530	Bank (IZhO14_bank)	C++20	100 / 100	100 ms	8520 KiB

bank

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define endl "\n";
#define all(x) x.begin(), x.end()
ll MOD = 1e9+7;

struct Obj {
	int used, soFar;
};


void solve() {
	int n, m; cin >> n >> m;
	if (n > m) {
		cout << "NO\n";
		return;
	}
	vector<int> people(n);
	for (int& i : people) {
		cin >> i;
	}
	vector<int> money(m);
	for (int& i : money) {
		cin >> i;
	}
	vector<Obj> dp((1 << m), {-1, -1});
	dp[0] = {0, 0};
	for (int mask = 0; mask < (1 << m); mask++) {
		if (dp[mask].used == -1) continue;
		if (dp[mask].used == n) {
			cout << "YES\n";
			return;
		}
		for (int i = 0; i < m; i++) {
			//cerr << mask << ' ' << i << endl;
			if (mask & (1 << i)) continue;
			ll newMask = mask | (1 << i);
			if (money[i] + dp[mask].soFar > people[dp[mask].used]) {
				continue;
			}
			if (money[i] + dp[mask].soFar == people[dp[mask].used]) {
				dp[newMask] = {dp[mask].used + 1, 0};
			} else {
				dp[newMask] = {dp[mask].used, money[i] + dp[mask].soFar};
			}
		}
	}
	cout << "NO\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("example.in", "r", stdin);
	//freopen("bank.out", "w", stdout);
	ll t = 1; //cin >> t;
	while (t--) {
		solve();
	}

}

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