Submission #1277371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277371		hlk28khuong	Bank (IZhO14_bank)	C++20	52 / 100	1096 ms	6960 KiB

bank

#include <bits/stdc++.h>

using namespace std;
const int mxn=1e2+7;

int a[mxn],b[mxn];
bool dp[22][(1LL << 20) + 2];
vector<int>state[20002];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>b[i];

    for(int mask=1;mask<(1<<m);mask++)
    {
        int musk = mask;
        int sum = 0;
        while(musk > 0){
            int i = __builtin_ctz(musk & -musk);
            sum += b[i + 1];
            musk -= (1LL<<i);
        }

        state[sum].push_back(mask);

    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int mask=0;mask<(1<<m);mask++)
        {
            for(auto musk:state[a[i]])
            {
                if((musk&mask)==0)
                {
                    dp[i][mask|musk]|=dp[i-1][mask];
                }
            }
        }
    }
    for(int mask=0;mask<(1<<m);mask++)
    {
        if(dp[n][mask])
        {
            cout<<"YES";
            return 0;
        }
    }
    cout<<"NO";
    return 0;
}

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