Submission #847284

#TimeUsernameProblemLanguageResultExecution timeMemory
847284c2zi6Bank (IZhO14_bank)C++14
19 / 100
442 ms136016 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int& x : a) cin >> x;
    for (int& x : b) cin >> x;

    const int MAXA = 1001;

    int dpc[1<<m]{};
    bitset<MAXA> dpp[1<<m];
    dpp[0] = bitset<MAXA>(1);
    for (int s = 1; s < (1<<m); s++) {
        int bestc = -1;
        bitset<MAXA> bestp;
        for (int i = 0; i < m; i++) {
            if (!(s & (1<<i))) continue;
            int ps = (s ^ (1<<i));
            int curc = dpc[ps];
            bitset<MAXA> curp = (dpp[ps]<<b[i]);
            if (curp[a[bestc]]) curc++, curp = bitset<MAXA>(1);
            if (curc > bestc) {
                bestc = curc;
                bestp = curp;
            } else if (curc == bestc) {
                bestp |= curp;
            }
            //cout << curc << " " << curp << endl;
        }
        dpc[s] = bestc;
        dpp[s] = bestp;
    }
    bool ans = false;
    for (int i = 0; i < (1<<m); i++) {
        if (dpc[i] == n) ans = true;
        //cout << dpc[i] << " : " << dpp[i] << endl;
    }
    if (ans) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main() {
    int t = 1;
    //cin >> t;
    while (t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...