Submission #1147411

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147411		AlgorithmWarrior	Bank (IZhO14_bank)	C++20	100 / 100	101 ms	8576 KiB

bank

#include <bits/stdc++.h>

using namespace std;

int n,m;
int a[23];
int b[23];

void read(){
    cin>>n>>m;
    int i;
    for(i=0;i<n;++i)
        cin>>a[i];
    for(i=0;i<m;++i)
        cin>>b[i];
}

struct plata{
    int ind,val;
    bool operator != (plata ot){
        return (ind!=ot.ind || val!=ot.val);
    }
    bool operator == (plata ot){
        return (ind==ot.ind && val==ot.val);
    }
}dp[1050000];

bool get_dp(){
    dp[0]={0,a[0]};
    plata imp={-1,0};
    int i,bit;
    for(i=1;i<(1<<m);++i){
        dp[i]=imp;
        for(bit=0;bit<m;++bit)
            if(i&(1<<bit)){
                int vechi=i^(1<<bit);
                int ind=dp[vechi].ind;
                int new_val=dp[vechi].val-b[bit];
                if(dp[vechi]!=imp && new_val>=0){
                    if(new_val){
                        dp[i].ind=ind;
                        dp[i].val=new_val;
                    }
                    else{
                        dp[i].ind=ind+1;
                        dp[i].val=a[ind+1];
                    }
                }
            }
    }
    plata complet={n,0};
    for(i=1;i<(1<<m);++i)
        if(dp[i]==complet)
            return 1;
    return 0;
}

void write(bool ans){
    cout<<((ans)?"YES":"NO");
}

int main()
{
    read();
    write(get_dp());
    return 0;
}

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