#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]]){
int k=mask&to;
if(k==to){
if(solution(mask^to,u+1)){
return dp[mask][u]=true;
}
}
}
return dp[mask][u]=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:39:35: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
39 | return dp[mask][u]=true;
| ~~~~~~~~~~~^~~~~
bank.cpp:43:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
43 | return dp[mask][u]=false;
| ~~~~~~~~~~~^~~~~~
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 |
82836 KB |
Output is correct |
2 |
Correct |
31 ms |
82832 KB |
Output is correct |
3 |
Correct |
34 ms |
82812 KB |
Output is correct |
4 |
Correct |
33 ms |
83024 KB |
Output is correct |
5 |
Correct |
94 ms |
89196 KB |
Output is correct |
6 |
Correct |
31 ms |
82772 KB |
Output is correct |
7 |
Correct |
31 ms |
82868 KB |
Output is correct |
8 |
Correct |
99 ms |
88560 KB |
Output is correct |
9 |
Correct |
94 ms |
88788 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
82772 KB |
Output is correct |
2 |
Correct |
30 ms |
82812 KB |
Output is correct |
3 |
Correct |
34 ms |
82860 KB |
Output is correct |
4 |
Correct |
32 ms |
82784 KB |
Output is correct |
5 |
Correct |
36 ms |
82772 KB |
Output is correct |
6 |
Correct |
36 ms |
82776 KB |
Output is correct |
7 |
Correct |
35 ms |
82796 KB |
Output is correct |
8 |
Correct |
31 ms |
82760 KB |
Output is correct |
9 |
Correct |
32 ms |
82836 KB |
Output is correct |
10 |
Correct |
31 ms |
82828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
32 ms |
82940 KB |
Output is correct |
2 |
Correct |
33 ms |
82932 KB |
Output is correct |
3 |
Correct |
33 ms |
83020 KB |
Output is correct |
4 |
Correct |
33 ms |
82864 KB |
Output is correct |
5 |
Correct |
32 ms |
82900 KB |
Output is correct |
6 |
Correct |
33 ms |
82948 KB |
Output is correct |
7 |
Correct |
32 ms |
82916 KB |
Output is correct |
8 |
Correct |
33 ms |
82924 KB |
Output is correct |
9 |
Correct |
33 ms |
82944 KB |
Output is correct |
10 |
Correct |
39 ms |
82924 KB |
Output is correct |
11 |
Correct |
33 ms |
82920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
82836 KB |
Output is correct |
2 |
Correct |
31 ms |
82832 KB |
Output is correct |
3 |
Correct |
34 ms |
82812 KB |
Output is correct |
4 |
Correct |
33 ms |
83024 KB |
Output is correct |
5 |
Correct |
94 ms |
89196 KB |
Output is correct |
6 |
Correct |
31 ms |
82772 KB |
Output is correct |
7 |
Correct |
31 ms |
82868 KB |
Output is correct |
8 |
Correct |
99 ms |
88560 KB |
Output is correct |
9 |
Correct |
94 ms |
88788 KB |
Output is correct |
10 |
Correct |
32 ms |
82772 KB |
Output is correct |
11 |
Correct |
30 ms |
82812 KB |
Output is correct |
12 |
Correct |
34 ms |
82860 KB |
Output is correct |
13 |
Correct |
32 ms |
82784 KB |
Output is correct |
14 |
Correct |
36 ms |
82772 KB |
Output is correct |
15 |
Correct |
36 ms |
82776 KB |
Output is correct |
16 |
Correct |
35 ms |
82796 KB |
Output is correct |
17 |
Correct |
31 ms |
82760 KB |
Output is correct |
18 |
Correct |
32 ms |
82836 KB |
Output is correct |
19 |
Correct |
31 ms |
82828 KB |
Output is correct |
20 |
Correct |
32 ms |
82940 KB |
Output is correct |
21 |
Correct |
33 ms |
82932 KB |
Output is correct |
22 |
Correct |
33 ms |
83020 KB |
Output is correct |
23 |
Correct |
33 ms |
82864 KB |
Output is correct |
24 |
Correct |
32 ms |
82900 KB |
Output is correct |
25 |
Correct |
33 ms |
82948 KB |
Output is correct |
26 |
Correct |
32 ms |
82916 KB |
Output is correct |
27 |
Correct |
33 ms |
82924 KB |
Output is correct |
28 |
Correct |
33 ms |
82944 KB |
Output is correct |
29 |
Correct |
39 ms |
82924 KB |
Output is correct |
30 |
Correct |
33 ms |
82920 KB |
Output is correct |
31 |
Correct |
99 ms |
89364 KB |
Output is correct |
32 |
Correct |
93 ms |
88652 KB |
Output is correct |
33 |
Correct |
99 ms |
88992 KB |
Output is correct |
34 |
Correct |
101 ms |
89376 KB |
Output is correct |
35 |
Correct |
113 ms |
90300 KB |
Output is correct |
36 |
Correct |
104 ms |
89824 KB |
Output is correct |
37 |
Correct |
99 ms |
90192 KB |
Output is correct |
38 |
Correct |
99 ms |
89900 KB |
Output is correct |
39 |
Correct |
95 ms |
87696 KB |
Output is correct |
40 |
Correct |
119 ms |
89804 KB |
Output is correct |
41 |
Correct |
100 ms |
89216 KB |
Output is correct |
42 |
Correct |
97 ms |
88268 KB |
Output is correct |
43 |
Correct |
97 ms |
90092 KB |
Output is correct |
44 |
Correct |
105 ms |
90296 KB |
Output is correct |
45 |
Correct |
101 ms |
89104 KB |
Output is correct |
46 |
Correct |
98 ms |
90148 KB |
Output is correct |
47 |
Correct |
101 ms |
89620 KB |
Output is correct |
48 |
Correct |
95 ms |
88496 KB |
Output is correct |
49 |
Correct |
93 ms |
88624 KB |
Output is correct |
50 |
Correct |
96 ms |
87692 KB |
Output is correct |
51 |
Correct |
91 ms |
88652 KB |
Output is correct |
52 |
Correct |
95 ms |
87680 KB |
Output is correct |
53 |
Correct |
96 ms |
87664 KB |
Output is correct |
54 |
Correct |
97 ms |
87724 KB |
Output is correct |
55 |
Correct |
103 ms |
87748 KB |
Output is correct |
56 |
Correct |
99 ms |
88300 KB |
Output is correct |
57 |
Correct |
323 ms |
88536 KB |
Output is correct |
58 |
Correct |
104 ms |
88376 KB |
Output is correct |