Submission #1346918

#TimeUsernameProblemLanguageResultExecution timeMemory
1346918eldorbek_008Bank (IZhO14_bank)C++20
100 / 100
93 ms16836 KiB
#include <iostream>
#include <vector>

using namespace std;

#define int int64_t

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) {
        return 0;
    }

    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<int> p_cov(1 << m, -1);
    vector<int> left(1 << m, -1);

    p_cov[0] = 0;
    left[0] = 0;

    for (int mask = 0; mask < (1 << m); mask++) {
        if (p_cov[mask] == -1) {
            continue;
        }

        for (int i = 0; i < m; i++) {
            if (!(mask & (1 << i))) {
                int n_mask = mask | (1 << i);
                int cur_p = p_cov[mask];

                if (cur_p == n) {
                    continue;
                }

                int tar = a[cur_p];
                int n_left = left[mask] + b[i];

                if (n_left < tar) {
                    p_cov[n_mask] = cur_p;
                    left[n_mask] = n_left;
                }
                if (n_left == tar) {
                    p_cov[n_mask] = cur_p + 1;
                    left[n_mask] = 0;
                }
            }
        }
    }

    bool ok = false;
    for (int mask = 0; mask < (1 << m); mask++) {
        if (p_cov[mask] == n) {
            ok = true;
            break;
        }
    }

    if (ok) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...