oj.uz

Submission #968297

# Submission time Handle Problem Language Result Execution time Memory
968297 2024-04-23T09:47:13 Z tset Bank (IZhO14_bank) C++14
19 / 100
 73 ms 444 KB 
#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

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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 70 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 73 ms 348 KB Output is correct
9 Correct 70 ms 348 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Incorrect 0 ms 344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 2 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 70 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 73 ms 348 KB Output is correct
9 Correct 70 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Incorrect 0 ms 344 KB Output isn't correct
14 Halted 0 ms 0 KB -