Submission #496089

#	Time	Username	Problem	Language	Result	Execution time	Memory
496089		shmad	Bank (IZhO14_bank)	C++17	100 / 100	150 ms	25224 KiB

bank

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvi = vt< vt<int> >;

const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 20);

int n, m;
vt<int> dp(LIM, -1), lft(LIM, -1), ans;

bool bit (int x, int i) {
	return (x >> i & 1);
}

bool check (int x) {
	return (x == n);
}

void solve () {
	cin >> n >> m;
	vt<int> a(n), b(m);
	for (int &i: a) cin >> i;
	for (int &i: b) cin >> i;
	dp[0] = lft[0] = 0;
	for (int mask = 0; mask < (1 << m); mask++) {
		for (int i = 0; i < m; i++) {
			if (bit(mask, i)) {
				int mask1 = mask ^ (1 << i);
				if (dp[mask1] == -1) continue;
				int cur = lft[mask1] + b[i], j = dp[mask1];
				if (cur < a[j]) dp[mask] = dp[mask1], lft[mask] = cur;
				if (cur == a[j]) dp[mask] = dp[mask1] + 1, lft[mask] = 0;
			}
		}
		ans.pb(dp[mask]);
	}                                
	cout << (any_of(all(ans), check) ? "YES" : "NO");
	cout << '\n';
}

bool testcases = 0;

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int test = 1;
    if (testcases) cin >> test;
    for (int cs = 1; cs <= test; cs++) {
        solve();
    }
}

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