#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int people_num, notes_num;
cin >> people_num >> notes_num;
vector<int> salaries(people_num), banknotes(notes_num);
for (int i = 0; i < people_num; ++i) cin >> salaries[i];
for (int i = 0; i < notes_num; ++i) cin >> banknotes[i];
vector<pair<int, int>> dp(1 << notes_num, {-1, -1});
dp[0] = {0, 0};
for (int mask = 1; mask < (1 << notes_num); ++mask){
for (int last = 0; last < notes_num; ++last){
if (!(mask & (1 << last))) continue;
int prev = mask ^ (1 << last);
if (dp[prev].first == -1) continue;
int new_amt = dp[prev].second + banknotes[last];
int curr_target = salaries[dp[prev].first];
if (new_amt < curr_target){
dp[mask].first = dp[prev].first;
dp[mask].second = new_amt;
}
else if (new_amt == curr_target){
dp[mask].first = dp[prev].first + 1;
dp[mask].second = 0;
}
}
if (dp[mask].first == people_num){
cout << "YES";
return 0;
}
}
cout << "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... |