#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> salary;
vector<int> banknotes;
vector<vector<bool>> 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 + 1, vector<bool>(1 << M, false));
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);
}
}
dp[0][0] = 1;
for (int i = 0; i < N; i++)
{
for (int mask = 0; mask < m; mask++)
{
if (dp[i][mask])
{
for (int &c : candidates[i])
{
if (!(mask & c))
{
dp[i + 1][mask | c] = true;
}
}
}
}
}
bool ans = false;
for (int i = 0; i < (1 << M); i++)
{
if (dp[N][i])
{
ans = true;
break;
}
}
cout << (ans ? "YES" : "NO");
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |