Submission #1270377

#TimeUsernameProblemLanguageResultExecution timeMemory
1270377zuz14Bank (IZhO14_bank)C++20
71 / 100
1095 ms536 KiB
#include <bits/stdc++.h>
#define F first
#define S second 
using namespace std;

int n, m;
long long salary[21], bank[21];
vector<int> ok[21];

bool dfs(int k, int mask){
    bool b, res=0;

    //cout<<k<<' '<<mask<<endl;
    if (k>=n || salary[k]==0) return 1;
    if (mask>=(1<<m)-1) return 0;
    for (int i:ok[k]) {
        b=1;
        //cout<<i<<endl;
        for (int j=0; j<m; j++){ 
            if ((i & (1<<j)) && (mask & (1<<j))) b=0;
        }
        //cout<<i<<' '<<b<<' '<<c<<endl;
        if (b) res=max(res, dfs(k+1, mask+i));
    }

    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    long long c;
    cin>>n>>m;
    for (int i=0; i<n; i++) cin>>salary[i];
    for (int i=0; i<m; i++) cin>>bank[i];

    for (int i=0; i<n; i++){
        for (int mask=1; mask<=(1<<m)-1; mask++){
            c=0;
            for (int j=0; j<m; j++) if (mask & (1<<j)) c+=bank[j];
            if (c==salary[i]) ok[i].push_back(mask);
            //cout<<mask<<' '<<c<<endl;
        }
    }

    bool b=dfs(0, 0);
    if (b) 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...