Submission #493501

#	Time	Username	Problem	Language	Result	Execution time	Memory
493501		reni	Bank (IZhO14_bank)	C++14	100 / 100	311 ms	172676 KiB

bank

#include<iostream>
#define endl '\n'
using namespace std;
long long dp[(1<<21)][21], a[1000], b[1000],n,m;
bool is=false;

void rec(long long sum,long long pos, long long mask)
{
    if(is)return;
    if(pos==n){is=true;return;}
    for(int i=0;i<m;i++)
    {
        if(sum>b[i] && ((mask&(1<<i))==0))
        {
            if(!dp[mask|(1<<i)][pos])rec(sum-b[i],pos,mask|(1<<i));
            dp[mask|(1<<i)][pos]=1;
        }
        else if(sum==b[i] && ((mask&(1<<i))==0))
        {
            if(!dp[mask|(1<<i)][pos+1])rec(a[pos+1],pos+1,mask|(1<<i));
            dp[mask|(1<<i)][pos+1]=1;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long i,j;

    cin>>n>>m;

    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(j=0;j<m;j++)
    {
        cin>>b[j];
    }

    rec(a[0],0,0);

    if(is)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;


}

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