Submission #1327792

#TimeUsernameProblemLanguageResultExecution timeMemory
1327792ImNoob0550Bank (IZhO14_bank)C++20
100 / 100
386 ms33748 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll a[21];
ll b[21];
ll f[(1<<20)];
bool f1[22][(1<<20)];
bool have[22];
vector<ll> v[200001];
int main()
{
    // freopen("flood.inp","r",stdin);
    // freopen("flood.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(ll i=0;i<n;i++)
    {
        cin >> a[i];
    }
    for(ll i=0;i<m;i++)
    {
        cin >> b[i];
    }
    for(ll mask=0;mask<(1<<m);mask++)
    {
        for(ll tmp=(1<<m)-1-mask;tmp>0;tmp^=tmp&(-tmp))
        {
            ll i=__builtin_ctz(tmp);
            f[(mask|(1<<i))]=f[mask]+b[i];
        }
        v[f[mask]].push_back(mask);
        // cout << f[mask] << ' ';
    }
    f1[0][0]=true;
    have[0]=true;
    for(ll i=0;i<n;i++)
    {
        for(ll mask=0;mask<(1<<m);mask++)
        {
            // cout << f1[i][mask] << ' ';
            if(!f1[i][mask])
            {
                continue;
            }
            for(auto j:v[a[i]])
            {
                if((j&mask)!=0)
                {
                    continue;
                }
                f1[i+1][(j|mask)]=true;
                have[i+1]=true;
            }
        }
        // cout << '\n';
    }
    if(have[n])
    {
        cout << "YES";
    }
    else
    {
        cout << "NO";
    }
    cout << '\n';
    // cout << '\n';
    return 0;
}
/*
2 6
9 14
5 4 8 6 3 11
By Do Nhat Nam's laptop :)
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...