Submission #1268217

#TimeUsernameProblemLanguageResultExecution timeMemory
1268217puc_playerBank (IZhO14_bank)C++20
100 / 100
216 ms86600 KiB
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> salary;
vector<int> banknotes;
vector<vector<int>> dp;
vector<vector<int>> candidates;

bool canAssign(int i, int mask)
{
    if (i == N)
    {
        return true;
    }
    if (dp[i][mask] != -1)
        return dp[i][mask];
    for (int &c : candidates[i])
    {
        if (!(mask & c))
        {
            if (canAssign(i + 1, mask | c))
                return dp[i][mask] = true;
        }
    }
    return dp[i][mask] = false;
}

int main()
{
    cin >> N >> M;
    salary.resize(N);
    banknotes.resize(M);

    for (int i = 0; i < N; ++i)
        cin >> salary[i];
    for (int i = 0; i < M; ++i)
        cin >> banknotes[i];

    dp.resize(N, vector<int>(1 << M, -1));
    candidates.resize(N);

    int m = 1 << M;
    for (int mask = 0; mask < m; mask++)
    {
        int sum = 0;
        for (int i = 0; i < M; i++)
        {
            if (mask & (1 << i))
                sum += banknotes[i];
        }
        for (int i = 0; i < N; i++)
        {
            if (sum == salary[i])
                candidates[i].push_back(mask);
        }
    }
    cout << (canAssign(0, 0) ? "YES" : "NO");
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...