제출 #640632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640632		gnhmhp	은행 (IZhO14_bank)	C++14	100 / 100	111 ms	8532 KiB

bank

#define taskname "bank."
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
using namespace std;

int n, m;
int a[20], b[20], dp[1<<20], c[1<<20];

int main()
{
    fastio;
    cin >> n >> m;
    for (int i=0; i<n; ++i) cin >> a[i];
    for (int i=0; i<m; ++i) cin >> b[i];
    for (int i=1; i<(1<<m); ++i) dp[i]=c[i]=-1;
    for (int mask=1; mask<(1<<m); ++mask)
    {
        for (int i=0; i<m; ++i)
        {
            if (!(mask&(1<<i))) continue;
            int x=mask^(1<<i);
            if (dp[x]==-1) continue;
            int s=c[x]+b[i];
            if (s==a[dp[x]])
                dp[mask]=dp[x]+1, c[mask]=0;
            else if (s<a[dp[x]])
                dp[mask]=dp[x], c[mask]=s;

        }
        if (dp[mask]==n)
        {
            cout << "YES"; return 0;
        }

    }
    cout << "NO";
}

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