Submission #593292

#	Time	Username	Problem	Language	Result	Execution time	Memory
593292		daisy2	Bank (IZhO14_bank)	C++14	100 / 100	199 ms	31568 KiB

bank

#include<iostream>
#include<algorithm>
using namespace std;
long long n,m,ppl[100],ban[100];
bool is[22][1100000],dp[22][1100000];
bool isposs(long long pers,long long tp,long long mask)
{
    if(pers==n) return 1;
    if(mask==((1<<m)-1)) return 0;
    if(is[pers][mask]) return dp[pers][mask];

    bool re=0;
    for(int i=0;i<m;i++)
    {
        if(ban[i]<=tp && ((1<<i)&mask)==0)
        {
            if(tp==ban[i])
              re=(re|(isposs(pers+1,ppl[pers+1],mask|(1<<i))));

            else
               re=(re|(isposs(pers,tp-ban[i],mask|(1<<i))));
        }
    }
    is[pers][mask]=1;
    return dp[pers][mask]=re;
}
int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++)
    {
        cin>>ppl[i];
    }
    for(int i=0;i<m;i++)
    {
        cin>>ban[i];
    }
    if(isposs(0,ppl[0],0)==0)
        cout<<"NO"<<endl;

    else cout<<"YES"<<endl;
}

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