Submission #798589

#	Time	Username	Problem	Language	Result	Execution time	Memory
798589		cryan	Bank (IZhO14_bank)	C++17	100 / 100	102 ms	8532 KiB

bank

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#include "bits/stdc++.h"
using namespace std;

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#define mp make_pair
#define f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifndef LOCAL
#define endl "\n"
#else
#include "/mnt/c/yukon/pp.hpp"
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m;
	cin >> n >> m;

	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	vector<int> b(m);
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}

	vector<pi> dp(1 << m, {-inf, -inf});

	dp[0] = {0, 0};

	for (int i = 1; i < (1 << m); i++) {
		for (int j = 0; j < m; j++) {
			if (i & (1 << j)) {
				int prev = i ^ (1 << j);
				if (dp[prev].f == -inf)
					continue;
				if (dp[prev].s + b[j] < a[dp[prev].f]) {
					dp[i] = dp[prev];
					dp[i].s += b[j];
				} else if (dp[prev].s + b[j] == a[dp[prev].f]) {
					dp[i] = dp[prev];
					dp[i].f++;
					dp[i].s = 0;
				}
			}
		}
		if (dp[i].f == n) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o
// math it out
// ok well X is always possible, how about X + 1 (etc.)

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