제출 #1327789

#제출 시각아이디문제언어결과실행 시간메모리
1327789ImNoob0550은행 (IZhO14_bank)C++20
19 / 100
25 ms20688 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;
    for(ll i=0;i<n;i++)
    {
        for(ll mask=0;mask<(1<<m);mask++)
        {
            if(!f1[i][mask])
            {
                break;
            }
            for(auto j:v[a[i]])
            {
                if((j&mask)!=0)
                {
                    continue;
                }
                f1[i+1][j|mask]=true;
                have[i+1]=true;
            }
        }
    }
    if(have[n])
    {
        cout << "YES";
    }
    else
    {
        cout << "NO";
    }
    cout << '\n';
    // cout << '\n';
    return 0;
}
/*
2 6
9 10
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...