제출 #541392

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

bank

#include <iostream>

using namespace std;

int n,m;
int a[22], b[22];

int dp[2000005], leftVal[2000005];

int main()
{
    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++)
    {
        dp[mask] = -1;
        leftVal[mask] = -1;
    }

    for(int mask=0; mask < (1<<m); mask++)
    {
        for(int last=0;last<m;last++)
        {
            if(((mask>>last)&1) == 0)
                continue;

            int prev = mask - (1<<last);

            if(dp[prev] == -1)
                continue;

            int nVal = leftVal[prev] + b[last+1];
            int target = a[ dp[prev] + 1 ];

            if(nVal < target)
            {
                dp[mask] = dp[prev];
                leftVal[mask] = nVal;
            }
            else if(nVal == target)
            {
                dp[mask] = dp[prev] + 1;
                leftVal[mask] = 0;
            }

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

    cout<<"NO";
    return 0;
}

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