Submission #1270405

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

const int N=(1<<20)+7;
int n, m;
long long salary[21], bank[21];
bool odw[N];

void dfs(int k, int mask, long long c){
    if (k>=n) {cout<<"YES"; exit(0);}

    bool b=0;
    int l=0;
    
    odw[mask]=1;
    for (int i=0; i<m; i++) if (!(mask & (1<<i))) l++;
    if (n-k>l) return;
    for (int i=0; i<m; i++) {
        if (!(mask & (1<<i)) && !odw[mask+(1<<i)]){
            if (c+bank[i]<salary[k]) dfs(k, mask+(1<<i), c+bank[i]);
            else if (c+bank[i]==salary[k]) dfs(k+1, mask+(1<<i), 0);
        }
    }
}

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];

    dfs(0, 0, 0);
    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...