제출 #876565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876565		tinnhiemnn	은행 (IZhO14_bank)	C++14	100 / 100	406 ms	190176 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define file "file"

long long n,m,i,j,s,t,a[25],w[25],dp[22][1100000];
vector<long long> v[25];

int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(); cin.tie();

    cin>>n>>m;
    for (i=1;i<=n;i++) cin>>a[i];

    for (i=0;i<m;i++) cin>>w[i];

    for (s=0;s<(1<<m);s++)
    {
        t=0;
        for (j=0;j<m;j++) if (s>>j & 1) t+=w[j];
        for (i=1;i<=n;i++) if (t==a[i]) v[i].push_back(s);
    }

    memset(dp, -1, sizeof dp); dp[0][0]=0;

    for (i=1;i<=n;i++)
        for (s=0;s<(1<<m);s++)
    {
        if (dp[i-1][s]!=0) continue;

        for (long long j : v[i])
        {
            if ((s&j)!=0) continue;

            dp[i][s | j]=0;
        }
    }

    for (s=0;s<(1<<m);s++) if (dp[n][s]==0) {cout<<"YES"; return 0;}
    cout<<"NO";
}

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