#include <bits/stdc++.h>
using namespace std;
const int N=20;
int n,m,ans;
int val[(1<<20)+5],dp[21][(1<<20)+5],pre[21];
int a[21],b[21];
vector<int>pos[20001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<m;i++)cin>>b[i];
for(int mask=0;mask<(1<<m);mask++)
{
int sum=0;
for(int j=0;j<m;j++)if(mask&(1<<j))sum+=b[j];
val[mask]=sum;
pos[sum].push_back(mask);
}
for(int i=0;i<n;i++)for(int mask=0;mask<(1<<m);mask++)
{
dp[i][mask]=-1;
if(i==0&&val[mask]==a[i])dp[i][mask]=1;
}
pre[0]=a[0];
for(int i=1;i<n;i++)
{
pre[i]=pre[i-1]+a[i];
for(int mask=0;mask<(1<<m);mask++){
if(val[mask]==pre[i])
{
for(auto mask1:pos[a[i]])
{
if(mask1<=mask&&(mask1&mask)==mask1)
dp[i][mask]=max(dp[i][mask],dp[i-1][(mask^mask1)]);
}
}
}
}
for(int mask=0;mask<(1<<m);mask++)ans=max(ans,dp[n-1][mask]);
if(ans==1)cout<<"YES";
else cout<<"NO";
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... |