Submission #1369703

#TimeUsernameProblemLanguageResultExecution timeMemory
1369703norrawichzzz은행 (IZhO14_bank)C++20
71 / 100
1099 ms82512 KiB
#include <bits/stdc++.h>
using namespace std;

const int mask = (1<<20);
int mem[20][mask];

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

bool fnd(int idx, int vst) {
    if (idx == n) return true;

    if (mem[idx][vst] != -1) return mem[idx][vst];

    bool ok=0;
    for (int i=0; i<(1<<m); i++) {
        if (i&vst) continue;

        int sm=0;
        for (int j=0; j<m; j++) {
            if (i & (1<<j)) {
                sm+=b[j];
            }
        }

        if (sm == a[idx]) {
            ok = ok || fnd(idx+1, (vst|i));
        }
    }
    return mem[idx][vst] = ok;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>> n>> m;

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

    for (int i=0; i<20; i++) for (int j=0; j<(1<<20); j++) mem[i][j] = -1;
    
    if (fnd(0, 0)) cout<< "YES";
    else cout<< "NO";
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...