Submission #968297

#	Time	Username	Problem	Language	Result	Execution time	Memory
968297		tset	Bank (IZhO14_bank)	C++14	19 / 100	73 ms	444 KiB

bank

#include<bits/stdc++.h>

using namespace std;

#define int long long


bool dp[(1<<20) +42][21];

signed main()
{
    int nbReq, nbBillets;
    scanf("%lld%lld", &nbReq, &nbBillets);
    const int MX = 1<<nbBillets;
    vector<int> req(nbReq);
    vector<int> billets(nbBillets);
    for(int i=0; i<nbReq; i++)
        scanf("%lld", &req[i]); 
    for(int i=0; i<nbBillets; i++)
        scanf("%lld", &billets[i]);
    vector<vector<int>> occ(nbReq);
    for(int mask=0; mask<=MX; mask++)
    {
        int sum = 0;
        for(int iB=0; iB<nbBillets; iB++)
        {
            if((mask&(1<<iB)) != 0)
            {
                sum += billets[iB];
            }
        }
        for(int iR =0; iR < nbReq; iR++)
        {
            if(req[iR] == sum)
            {
                occ[iR].push_back(mask);
            }
        }
    }

    dp[0][0] = true;
    for(int iR =0; iR < nbReq; iR++)
    {
        for(int mask= 0; mask<= MX; mask++)
        {
            if(dp[iR][mask])
            {
                for(int addMask : occ[iR])
                {
                    if((mask & addMask) == 0)
                    {
                        dp[iR+1][mask|addMask] = true;
                        if(iR+1 == nbReq)
                        {
                            printf("YES\n");
                            exit(0);
                        }
                    }
                }
            }
        }
    }
    
    printf("NO\n");
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%lld%lld", &nbReq, &nbBillets);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         scanf("%lld", &req[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
bank.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%lld", &billets[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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