#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<int> b(m);
for (int &x : b) cin >> x;
int ALL = 1 << m;
vector<int> sum(ALL, 0);
for (int mask = 1; mask < ALL; mask++) {
int lb = __builtin_ctz(mask);
sum[mask] = sum[mask ^ (1<<lb)] + b[lb];
}
// danh sách submask có tổng = x
unordered_map<int, vector<int>> subs;
for (int mask = 0; mask < ALL; mask++) {
subs[sum[mask]].push_back(mask);
}
vector<vector<char>> dp(n+1, vector<char>(ALL, 0));
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
for (int mask = 0; mask < ALL; mask++) if (dp[i][mask]) {
for (int sub : subs[a[i]]) {
if ((mask & sub) == 0) {
dp[i+1][mask | sub] = 1;
}
}
}
}
bool ok = false;
for (int mask = 0; mask < ALL; mask++) {
if (dp[n][mask]) ok = true;
}
cout << (ok ? "YES\n" : "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... |