Submission #1316293

#TimeUsernameProblemLanguageResultExecution timeMemory
1316293nambanana987Bank (IZhO14_bank)C++20
19 / 100
94 ms16820 KiB
#include <bits/stdc++.h>
#include <climits>
using namespace std;
#define f first
#define s second
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define int long long
const int N=21;
const int MaxBit=1<<N;
const int INF=INT_MAX;
int salary[N];// lương cần trả
int comp[N]; // tiền công ty có
int n,m;
int peo[MaxBit];
int have[MaxBit];

void solve(){
    cin>>n>>m;
    for(int i=0;i<n;++i) cin>>salary[i];
    for(int i=0;i<m;++i) cin>>comp[i];

    for(int mask=1;mask<(1<<n);++mask){
        peo[mask]=INF;
        have[mask]=INF;
    }
    for(int mask=1;mask<(1<<m);++mask){
        for(int i=0;i<m;++i){
            if(!(mask&(1<<i))) continue;
            if(have[mask & ~(1<<i)]==INF) continue;

            int pre_peo=peo[mask^(1<<i)],pre_have=have[mask^(1<<i)];

            if(pre_have+comp[i]==salary[pre_peo]){
                have[mask]=0;
                peo[mask]=pre_peo+1;
            }
            if(pre_have+comp[i]<salary[pre_peo]){
                have[mask]=pre_have+comp[i];
                peo[mask]=pre_peo;
            }
        }
        if(peo[mask]==n){
            cout<<"YES";
            return;
        }
    }
    cout<<"NO";
}
signed main(){

    ios_base::sync_with_stdio(0);cin.tie(0);
    int T=1;
    while(T--) 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...