#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;
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:40:35: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
40 | return dp[mask][u]=true;
| ~~~~~~~~~~~^~~~~
bank.cpp:44:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
44 | return dp[mask][u]=false;
| ~~~~~~~~~~~^~~~~~
bank.cpp: In function 'void solve()':
bank.cpp:68:34: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
68 | bool res=solution((1<<m)-1,0)<<ln;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
82744 KB |
Output is correct |
2 |
Correct |
31 ms |
82880 KB |
Output is correct |
3 |
Correct |
30 ms |
82772 KB |
Output is correct |
4 |
Correct |
34 ms |
83028 KB |
Output is correct |
5 |
Correct |
92 ms |
89212 KB |
Output is correct |
6 |
Correct |
32 ms |
82780 KB |
Output is correct |
7 |
Correct |
30 ms |
82836 KB |
Output is correct |
8 |
Correct |
92 ms |
88516 KB |
Output is correct |
9 |
Correct |
93 ms |
88796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
82752 KB |
Output is correct |
2 |
Correct |
32 ms |
82868 KB |
Output is correct |
3 |
Correct |
33 ms |
82824 KB |
Output is correct |
4 |
Correct |
34 ms |
82844 KB |
Output is correct |
5 |
Correct |
32 ms |
82760 KB |
Output is correct |
6 |
Correct |
33 ms |
82772 KB |
Output is correct |
7 |
Correct |
34 ms |
82772 KB |
Output is correct |
8 |
Correct |
32 ms |
82812 KB |
Output is correct |
9 |
Correct |
32 ms |
82772 KB |
Output is correct |
10 |
Correct |
33 ms |
82848 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
82932 KB |
Output is correct |
2 |
Correct |
34 ms |
82912 KB |
Output is correct |
3 |
Correct |
33 ms |
83044 KB |
Output is correct |
4 |
Correct |
34 ms |
82892 KB |
Output is correct |
5 |
Correct |
32 ms |
82916 KB |
Output is correct |
6 |
Correct |
33 ms |
83060 KB |
Output is correct |
7 |
Correct |
32 ms |
82892 KB |
Output is correct |
8 |
Correct |
33 ms |
82976 KB |
Output is correct |
9 |
Correct |
33 ms |
83020 KB |
Output is correct |
10 |
Correct |
38 ms |
82940 KB |
Output is correct |
11 |
Correct |
33 ms |
82828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
82744 KB |
Output is correct |
2 |
Correct |
31 ms |
82880 KB |
Output is correct |
3 |
Correct |
30 ms |
82772 KB |
Output is correct |
4 |
Correct |
34 ms |
83028 KB |
Output is correct |
5 |
Correct |
92 ms |
89212 KB |
Output is correct |
6 |
Correct |
32 ms |
82780 KB |
Output is correct |
7 |
Correct |
30 ms |
82836 KB |
Output is correct |
8 |
Correct |
92 ms |
88516 KB |
Output is correct |
9 |
Correct |
93 ms |
88796 KB |
Output is correct |
10 |
Correct |
36 ms |
82752 KB |
Output is correct |
11 |
Correct |
32 ms |
82868 KB |
Output is correct |
12 |
Correct |
33 ms |
82824 KB |
Output is correct |
13 |
Correct |
34 ms |
82844 KB |
Output is correct |
14 |
Correct |
32 ms |
82760 KB |
Output is correct |
15 |
Correct |
33 ms |
82772 KB |
Output is correct |
16 |
Correct |
34 ms |
82772 KB |
Output is correct |
17 |
Correct |
32 ms |
82812 KB |
Output is correct |
18 |
Correct |
32 ms |
82772 KB |
Output is correct |
19 |
Correct |
33 ms |
82848 KB |
Output is correct |
20 |
Correct |
34 ms |
82932 KB |
Output is correct |
21 |
Correct |
34 ms |
82912 KB |
Output is correct |
22 |
Correct |
33 ms |
83044 KB |
Output is correct |
23 |
Correct |
34 ms |
82892 KB |
Output is correct |
24 |
Correct |
32 ms |
82916 KB |
Output is correct |
25 |
Correct |
33 ms |
83060 KB |
Output is correct |
26 |
Correct |
32 ms |
82892 KB |
Output is correct |
27 |
Correct |
33 ms |
82976 KB |
Output is correct |
28 |
Correct |
33 ms |
83020 KB |
Output is correct |
29 |
Correct |
38 ms |
82940 KB |
Output is correct |
30 |
Correct |
33 ms |
82828 KB |
Output is correct |
31 |
Correct |
95 ms |
89360 KB |
Output is correct |
32 |
Correct |
96 ms |
88596 KB |
Output is correct |
33 |
Correct |
100 ms |
89176 KB |
Output is correct |
34 |
Correct |
100 ms |
89356 KB |
Output is correct |
35 |
Correct |
107 ms |
90344 KB |
Output is correct |
36 |
Correct |
108 ms |
89820 KB |
Output is correct |
37 |
Correct |
100 ms |
90220 KB |
Output is correct |
38 |
Correct |
99 ms |
89860 KB |
Output is correct |
39 |
Correct |
97 ms |
87756 KB |
Output is correct |
40 |
Correct |
118 ms |
89744 KB |
Output is correct |
41 |
Correct |
107 ms |
89220 KB |
Output is correct |
42 |
Correct |
102 ms |
88208 KB |
Output is correct |
43 |
Correct |
102 ms |
90060 KB |
Output is correct |
44 |
Correct |
113 ms |
90252 KB |
Output is correct |
45 |
Correct |
98 ms |
89100 KB |
Output is correct |
46 |
Correct |
105 ms |
90112 KB |
Output is correct |
47 |
Correct |
111 ms |
89692 KB |
Output is correct |
48 |
Correct |
95 ms |
88524 KB |
Output is correct |
49 |
Correct |
97 ms |
88652 KB |
Output is correct |
50 |
Correct |
101 ms |
87696 KB |
Output is correct |
51 |
Correct |
98 ms |
88660 KB |
Output is correct |
52 |
Correct |
95 ms |
87712 KB |
Output is correct |
53 |
Correct |
101 ms |
87660 KB |
Output is correct |
54 |
Correct |
97 ms |
87716 KB |
Output is correct |
55 |
Correct |
96 ms |
87752 KB |
Output is correct |
56 |
Correct |
94 ms |
88412 KB |
Output is correct |
57 |
Correct |
332 ms |
88336 KB |
Output is correct |
58 |
Correct |
102 ms |
88380 KB |
Output is correct |