Submission #1014673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014673		MMihalev	Bank (IZhO14_bank)	C++14	0 / 100	14 ms	348 KiB

bank

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<tuple>
#include<set>
#include<map>
#include<random>
#include<chrono>
#pragma GCC optimize ("unroll-loops")
using namespace std;
const int MAX_N=20;
short dp[(1<<MAX_N)];
short cost[(1<<MAX_N)];
int n,m;
short a[MAX_N];
short b[MAX_N];
signed main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>m;

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

    dp[0]=-1;

    for(int mask=1;mask<(1<<m);mask++)
    {
        dp[mask]=-1;

        for(int bit=0;bit<m;bit++)
        {
            if((1<<bit)&mask!=0)
            {
                cost[mask]+=b[bit];
            }
        }
        if(cost[mask]==a[0] && n==1)
        {
            cout<<"YES\n";
            return 0;
        }
    }

    if(n==1){cout<<"NO\n";return 0;}

    for(int mask=1;mask<(1<<m);mask++)
    {
        for(int submask=mask;submask;submask=(submask-1)&mask)
        {
            if(a[dp[mask & ~submask]+1]==cost[submask])
            {
                dp[mask]=max(dp[mask],(short)(dp[mask & ~submask]+1));
            }
            else dp[mask]=max(dp[mask],dp[mask & ~submask]);
        }
    }

    if(dp[(1<<m)-1]==n-1)cout<<"YES\n";
    else cout<<"NO\n";

    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:47:29: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   47 |             if((1<<bit)&mask!=0)
      |                         ~~~~^~~

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