// When she's prettier than any DP you've ever seen...
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n,m; cin >> n >> m;
int a[n+1], b[m], suma[1<<m];
bool dp[1<<m], odp = false; dp[0] = true;
a[0] = suma[0] = 0;
for (int i = 1; i <= n; i++)
cin >> a[i], a[i] += a[i-1];
for (int i = 0; i < m; i++)
cin >> b[i];
for (int mask = 1; mask < (1<<m); mask++) {
int bit = __builtin_ctz(mask);
dp[mask] = false, suma[mask] = b[bit]+suma[mask^(1<<bit)];
}
for (int k = 1; k <= n; k++) {
for (int mask = 0; mask < (1<<m); mask++) {
if (suma[mask] < a[k-1] || suma[mask] > a[k])
continue;
for (int i = 0; i < m; i++)
if (mask&(1<<i))
dp[mask] = (dp[mask] || dp[mask^(1<<i)]);
}
for (int mask = 0; mask < (1<<m); mask++)
if (suma[mask] != a[k])
dp[mask] = false;
}
for (int mask = 0; mask < (1<<m); mask++)
odp = (odp || dp[mask]);
cout << ((odp) ? "YES" : "NO") << endl;
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... |