#include <bits/stdc++.h>
using namespace std;
void setup()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int maxn = 2e4 + 1;
int n, m;
int a[20], b[20];
bool appear[1 << 20], cur[1 << 20];
vector<int> mask[maxn];
int main()
{
setup();
cin >> n >> m;
for (int i = 0; i < n; ++i)
{
cin >> a[i];
a[i] += (i == 0 ? 0 : a[i - 1]);
}
for (int i = 0; i < m; ++i)
{
cin >> b[i];
}
for (int i = 0, j; i < (1 << m); ++i)
{
j = 0;
for (int k = 0; k < m; ++k)
{
j += ((i >> k) & 1) * b[k];
}
mask[j].push_back(i);
}
appear[0] = 1;
for (int i = 1, j = 0; i < maxn && j < n; ++i)
{
if (i == a[j])
{
fill_n(cur, 1 << 20, 0);
for (auto &k : mask[i])
{
for (int h = 0; h < m; ++h)
{
if (((k >> h) & 1) && appear[k - (1 << h)])
{
cur[k] |= appear[k - (1 << h)];
}
}
}
if (i == a[j])
{
fill_n(appear, 1 << 20, 0);
j++;
}
for (int k = 0; k < (1 << 20); ++k)
{
appear[k] |= cur[k];
}
}
else
{
for (auto &k : mask[i])
{
for (int h = 0; h < m; ++h)
{
if (((k >> h) & 1) && appear[k - (1 << h)])
{
appear[k] |= appear[k - (1 << h)];
}
}
}
}
}
cout << ((*max_element(appear, appear + (1 << m))) == 0 ? "NO" : "YES");
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... |