제출 #1277373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277373		hlk28khuong	은행 (IZhO14_bank)	C++20	100 / 100	292 ms	20500 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++)
        {
            if(!dp[i-1][mask])continue;
            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: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29