Submission #1332853

#TimeUsernameProblemLanguageResultExecution timeMemory
1332853kamilaBank (IZhO14_bank)C++20
71 / 100
1095 ms892 KiB
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9+7, N=(1<<21);
#define all(x) x.begin(),x.end()
#define fr first
#define sc second
#define pb push_back
#define ret return
#define int long long
int v[25], b[25], dp[1<<22];
vector <int> d[25], g[25];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n, m, k, i,j, mask;  //HHH
    cin >>n>>m;
    for (i=0; i<n; ++i){
        cin >>v[i];
    }
    for (i=0; i<m; ++i){
        cin >>b[i];
    }

    for (i=0; i<n; ++i){
        for (mask=0; mask<(1<<m); ++mask){
            int sum=0;
            for (j=0; j<32; ++j){
                if (mask&(1<<j)){
                    sum+=b[j];
                }
            }
            if (sum==v[i]){
                d[i].pb(mask);
            }
        }
    }
    for (int x: d[0]){
        g[0].pb(x);
    }
    for (i=1; i<n; ++i){
        set <int> seen;
        for (int mask : g[i-1]){
            for (int nw : d[i]){
                if (!(mask&nw)){
                    int newm=mask|nw;
                    if (seen.insert(newm).second){
                    g[i].pb(newm);
                    }
                }
            }
        }
    }
    if (g[n-1].size())cout<<"YES";
    else cout <<"NO";
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...