Submission #420373

#TimeUsernameProblemLanguageResultExecution timeMemory
420373Runtime_error_은행 (IZhO14_bank)C++14
100 / 100
897 ms172764 KiB

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int inf = 21;
int a[inf],b[inf],n,m;
int dp[inf][(1<<inf)];
vector<int> v;

void bt(int coin,int mask,int SalaryLeft){
    if(SalaryLeft < 0)return ;
    if(coin == m){
        if(SalaryLeft == 0)
            v.pb(mask);
        return ;
    }
    bt(coin+1,mask,SalaryLeft);
    if(!((1<<coin)&mask))
        bt(coin+1,mask|(1<<coin),SalaryLeft-b[coin]);

}

int solve(int salary,int mask){
    if(salary == n)
        return 1;
    int &ret = dp[salary][mask];
    if(ret != -1)
        return ret;
    ret = 0;
    v.clear();
    bt(0,mask,a[salary]);
    vector<int> ValidMasks = v;

    for(auto o:ValidMasks)
        if(solve(salary+1,o))
            return ret = 1;
    return ret;
}


int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
        cin>>b[i];
    memset(dp,-1,sizeof(dp));
    int ans = solve(0,0);
    if(ans)
        puts("YES");
    else puts("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...