This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> salaries(n), bills(m);
for(int i = 0; i < n; ++i) {
cin >> salaries[i];
}
for(int i = 0; i < m; ++i) {
cin >> bills[i];
}
vector<int> dp(1 << n), last_value(1 << n);
dp[0] = -1;
last_value[0] = 0;
for (int s = 0; s < (1 << n); ++s) {
for (int j = 0; j < n; ++j) {
if (!((1 << j) & s))
continue;
int prev_set = (1 << j) ^ s;
int last_pos = dp[prev_set];
if (dp[s] == n - 1 || last_pos == n - 1) {
cout << "YES\n";
return 0;
}
if(salaries[last_pos + 1] == bills[j] + last_value[prev_set]) {
if(dp[prev_set] + 1 >= dp[s]) {
last_value[s] = 0;
}
dp[s] = max(dp[s], dp[prev_set] + 1);
continue;
}
last_value[s] = last_value[prev_set] + bills[j];
}
}
cout << "NO\n";
}
# | 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... |