///////////////////////////////////////////
// //
// CODE BY THE phantomstar3.14 //
// //
///////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ull unsigned long long
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
constexpr int V = 1E9;
constexpr int MAXN=1e9;
const int mod=1e9+7;
void solve()
{
int n,m;
cin>>n>>m;
vector<int> a(n,0), b(m,0);
for(int i=0; i<n; i++) cin>>a[i];
for(int i=0; i<m; i++) cin>>b[i];
bool dp[(1ll<<m)+1][n+1];
memset(dp, false, sizeof(dp));
for(int i=0; i<(1ll<<n); i++)
dp[i][0]=true;
for(int i=0; i<(1ll<<m); i++)
{
for(int j=i; j!=0; j=(j-1)&i)
{
int subset=(j^i);
int sum=0;
for(int k=0; k<m; k++)
{
if((1ll<<k) & subset)
sum+=b[k];
}
for(int k=1; k<=n; k++)
{
if(sum!=a[k-1]) continue;
dp[i][k]|=(dp[i][k]|dp[j][k-1]);
}
}
}
for(int i=0; i<(1ll<<m); i++)
{
if(dp[i][n])
{
cout<<"YES\n";
return;
}
}
cout<<"NO\n";
}
int32_t main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
auto begin = std::chrono::high_resolution_clock::now();
//freopen("piggyback.in", "r", stdin);
//freopen("piggyback.out", "w", stdout);
int t=1;
//cin >> t;
while (t--)
{
solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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... |