Submission #420373

#	Time	Username	Problem	Language	Result	Execution time	Memory
420373		Runtime_error_	Bank (IZhO14_bank)	C++14	100 / 100	897 ms	172764 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> 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");
}

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