Submission #420361

#	Time	Username	Problem	Language	Result	Execution time	Memory
420361		Runtime_error_	Bank (IZhO14_bank)	C++14	71 / 100	100 ms	172740 KiB

bank

#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");
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29