#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n+1), b(m+1);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
vector<pair<int, int>> dp((1<<(m+1))+1, {-1, -1});
// dp[mask].first stores the maximum prefix of salaries that the banknotes in the mask can pay
// dp[mask].second stores the leftover sum of banknotes after the first dp[mask].first salaries have been paid
dp[0] = {0, 0};
bool poss = false;
for (int mask = 0; mask < (1<<(m+1)); mask++) {
for (int last = 1; last <= m; last++) {
if (mask & (1<<last)) {
int m2 = mask ^ (1<<last);
if (dp[m2].first != -1) {
if (a[dp[m2].first+1] == dp[m2].second+b[last]) {
dp[mask].first = dp[m2].first+1;
dp[mask].second = 0;
}
else if (a[dp[m2].first+1] > dp[m2].second+b[last]) {
dp[mask].first = dp[m2].first;
dp[mask].second = dp[m2].second+b[last];
}
}
}
}
if (dp[mask].first == n) {
poss = true;
break;
}
}
if (poss) cout << "YES\n";
else cout << "NO\n";
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... |