Submission #1248321

#TimeUsernameProblemLanguageResultExecution timeMemory
1248321e_n1cat_Bank (IZhO14_bank)C++20
52 / 100
1093 ms1768 KiB
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll

const int sz = 25;
const int mod = 1e9 + 9;

int a[sz], b[sz];
bool dp[20+1][(1<<20)];

void solve(){
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];
    vector<int> v[25];
    dp[0][0] = true;
    for(int mask = 1; mask < (1 << m); mask++){
        dp[0][mask] = true;
        int cem = 0;
        for(int j = 0; j < m; j++){
            if((1 << j) & mask) cem += b[j];
        }
        for(int i = 1; i <= n; i++){
            if(a[i] == cem) v[i].push_back(mask);
        }
    }
    for(int i = 1; i <= n; i++){
        for(int mask = 1; mask < (1<<m); mask++){
            for(auto mask2: v[i]){
                if((mask2 & mask) == mask2){
                    dp[i][mask] |= dp[i-1][mask ^ mask2];
                }
                if(dp[i][mask]) break;
            }
        }
    }
    cout << (dp[n][(1<<m) - 1] ? "YES" : "NO") << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0); 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...