Submission #476425

#	Time	Username	Problem	Language	Result	Execution time	Memory
476425		Croco	Bank (IZhO14_bank)	C++17	100 / 100	353 ms	172748 KiB

bank

#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";
}

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