제출 #476425

#제출 시각아이디문제언어결과실행 시간메모리
476425Croco은행 (IZhO14_bank)C++17
100 / 100
353 ms172748 KiB
#include <bits/stdc++.h>
#define int long long int
#define ll long long

using namespace std;

const int N = 2e5 + 5;

int dp[(1<<20) + 1][21];

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

bool solve(int mask,int i,int left)
{
    if(i == n)
        return 1;
    if(~dp[mask][i])
        return dp[mask][i];
    int &res = dp[mask][i];
    res = 0;
    for(int j=0;j<m;j++)
    {
        if(mask & (1<<j))
            continue;
        if(b[j] <= left)
        {
            if(b[j] == left)
                res |= solve(mask | (1<<j),i + 1,a[i+1]);
            else
                res |= solve(mask | (1<<j),i,left - b[j]);
        }
    }
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    memset(dp,-1,sizeof dp);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
        cin>>b[i];
    if(solve(0,0,a[0]))
        cout << "YES";
    else
        cout << "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...