Submission #593295

#	Time	Username	Problem	Language	Result	Execution time	Memory
593295		Summers	Bank (IZhO14_bank)	C++14	100 / 100	305 ms	198484 KiB

bank

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
long long a[1100000], b[1100000], dp[1100000][23], n, m;

bool rec(long long mask,long long price,long long num)
{
   // cout<<mask<<" "<<price<<" "<<num<<endl;
    if(num==n+1)return 1;

    if(dp[mask][num]!=-1)return dp[mask][num];

    bool maxi=0;

    for(int i=1;i<=m;i++)
    {
        //cout<<b[i]<<" "<<endl;
        if(price>b[i] && !(mask&(1<<(i-1))))
        {//cout<<1;
            maxi=max(maxi,rec(mask|(1<<(i-1)),price-b[i],num));
        }
        if(price==b[i] && !(mask&(1<<(i-1))))
        {//cout<<1;
            maxi=max(maxi,rec(mask|(1<<(i-1)),a[num+1],num+1));
        }
    }
    return dp[mask][num]=maxi;
}

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

    long long i,j,k;

    cin>>n>>m;

    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(j=1;j<=m;j++)
    {
        cin>>b[j];
    }
    memset(dp,-1,sizeof(dp));

    if(rec(0,a[1],1))cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

Compilation message (stderr)

bank.cpp: In function 'bool rec(long long int, long long int, long long int)':
bank.cpp:27:25: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   27 |     return dp[mask][num]=maxi;
      |            ~~~~~~~~~~~~~^~~~~
bank.cpp: In function 'int main()':
bank.cpp:36:19: warning: unused variable 'k' [-Wunused-variable]
   36 |     long long i,j,k;
      |                   ^

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