Submission #1104794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104794		anmattroi	Bank (IZhO14_bank)	C++14	100 / 100	112 ms	8592 KiB

bank

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

typedef pair<int, int> ii;

int n, m;
int a[25], b[25];

ii f[1<<20];

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

ii calc(ii x, int y) {
    if (x.fi == n+1) return x;
    if (x.se + y > a[x.fi]) return {-1, -1};
    if (x.se + y == a[x.fi]) return {x.fi+1, 0};
    return {x.fi, x.se+y};
}

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];

    f[0] = {1, 0};
    for (int o = 1; o < (1<<m); o++) {
        f[o] = {-1, -1};
        for (int i = 1; i <= m; i++) {
            if (!bit(o, i-1)) continue;
            int y = o^(1<<(i-1));
            if (f[y] == ii{-1, -1}) continue;

            f[o] = max(f[o], calc(f[y], b[i]));
        }
    }
    ii X = f[(1<<m)-1];
    cout << (X.fi != n + 1 ? "NO" : "YES");
}

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