#include<bits/stdc++.h>
#define INF 1e9+7
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define pdd pair<double,double>
#define pipii pair<int,pii>
#define plpll pair<ll,pll>
#define vi vector<int>
#define vvi vector<vi>
#define v3i vector<vvi>
#define v4i vector<v3i>
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ins insert
#define ln '\n'
#define all(v) v.begin(),v.end()
using namespace std;
const int up=(1<<20);
int n,m;
vvi total_sum(20001);
int a[20],b[20];
int dp[up][20];
bool solution(int mask,int u){
if(u==n){
return true;
}
// if(dp[mask][u]!=-1) return dp[mask][u];
for(auto to:total_sum[a[u]]){
//cout<<mask<<" "<<to<<ln;
if(mask&to==to){
if(solution(mask^to,u+1)){
return true;
}
}
}
return false;
}
void solve(){
//ifstream cin("bank.in");
//ofstream cout("bank.out");
memset(dp,-1,sizeof(dp));
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=1;mask<(1<<m);++mask){
int sum=0;
for(int j=0;j<m;++j){
if(mask&(1<<j)){
sum+=b[j];
}
}
//cout<<sum<<" "<<mask<<ln;
total_sum[sum].eb(mask);
}
bool res=solution((1<<m)-1,0)<<ln;
//cout<<res<<ln;
if(res){
cout<<"YES"<<ln;
}
else{
cout<<"NO"<<ln;
}
//cin.close();
//cout.close();
}
int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++){
solve();
}
}
/*
10 10
0 1 10 100
1 1 5 3
1 7 9 8
0 1 10 9
2 1 2 3
2 9 4
0 1 10 100
1 1 10 2
0 1 10 1000
2 1 5 2
0 1 6
1
0
ll
10
1 2
2 4
4 8
4 9
2 5
1 3
3 6
6 10
3 7
*/
Compilation message
bank.cpp: In function 'bool solution(int, int)':
bank.cpp:37:19: warning: self-comparison always evaluates to true [-Wtautological-compare]
37 | if(mask&to==to){
| ~~^~~~
bank.cpp:37:19: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
37 | if(mask&to==to){
| ~~^~~~
bank.cpp: In function 'void solve()':
bank.cpp:67:34: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
67 | bool res=solution((1<<m)-1,0)<<ln;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
82760 KB |
Output is correct |
2 |
Correct |
33 ms |
82836 KB |
Output is correct |
3 |
Correct |
35 ms |
82836 KB |
Output is correct |
4 |
Correct |
39 ms |
83040 KB |
Output is correct |
5 |
Correct |
99 ms |
89116 KB |
Output is correct |
6 |
Correct |
31 ms |
82900 KB |
Output is correct |
7 |
Correct |
34 ms |
82868 KB |
Output is correct |
8 |
Correct |
98 ms |
88556 KB |
Output is correct |
9 |
Correct |
98 ms |
88852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
82776 KB |
Output is correct |
2 |
Correct |
31 ms |
82748 KB |
Output is correct |
3 |
Correct |
32 ms |
82800 KB |
Output is correct |
4 |
Incorrect |
35 ms |
82860 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
82940 KB |
Output is correct |
2 |
Correct |
34 ms |
82968 KB |
Output is correct |
3 |
Incorrect |
35 ms |
82972 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
82760 KB |
Output is correct |
2 |
Correct |
33 ms |
82836 KB |
Output is correct |
3 |
Correct |
35 ms |
82836 KB |
Output is correct |
4 |
Correct |
39 ms |
83040 KB |
Output is correct |
5 |
Correct |
99 ms |
89116 KB |
Output is correct |
6 |
Correct |
31 ms |
82900 KB |
Output is correct |
7 |
Correct |
34 ms |
82868 KB |
Output is correct |
8 |
Correct |
98 ms |
88556 KB |
Output is correct |
9 |
Correct |
98 ms |
88852 KB |
Output is correct |
10 |
Correct |
30 ms |
82776 KB |
Output is correct |
11 |
Correct |
31 ms |
82748 KB |
Output is correct |
12 |
Correct |
32 ms |
82800 KB |
Output is correct |
13 |
Incorrect |
35 ms |
82860 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |