#include <iostream>
#include <vector>
using namespace std;
const int N = 22;
const int M = 1010;
const int LIM = (1 << 20) + 10;
int n, m, a[N], b[N];
vector <int> v[M];
bool dp[2][LIM];
int main() {
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 0; i < m; ++i) cin >> b[i];
for (int i = 0; i < (1 << m); ++i) {
int sum = 0;
for (int j = 0; j < m; ++j) {
if (i >> j & 1) sum += b[j];
if (sum > 1000) break;
}
if (sum <= 1000) v[sum].push_back(i);
}
dp[1][(1 << m) - 1] = true;
for (int i = 1; i <= n; ++i) {
int b = i & 1;
fill_n(dp[b ^ 1], (1 << m), false);
for (int mask = 0; mask < (1 << m); ++mask) {
if (!dp[b][mask]) continue;
for (int z: v[a[i]]) {
if ((mask & z) == z) dp[b ^ 1][mask ^ z] = true;
}
}
}
int b = (n & 1) ^ 1;
for (int i = 0; i < (1 << m); ++i) {
if (dp[b][i]) {
cout << "YES\n";
return 0;
}
}
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... |