Submission #420361

#TimeUsernameProblemLanguageResultExecution timeMemory
420361Runtime_error_Bank (IZhO14_bank)C++14
71 / 100
100 ms172740 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> ValidMasks;

void go(int coin,int mask,int SalaryLeft){
    if(SalaryLeft < 0)return ;
    if(coin == m){
        if(SalaryLeft == 0)
            ValidMasks.pb(mask);
        return ;
    }
    go(coin+1,mask,SalaryLeft);
    if(!((1<<coin)&mask))
        go(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;
    ValidMasks.clear();
    go(0,mask,a[salary]);
    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...