#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 dp[mask][u]=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:39:35: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
39 | return dp[mask][u]=true;
| ~~~~~~~~~~~^~~~~
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 |
Incorrect |
32 ms |
82744 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
34 ms |
82760 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
33 ms |
82768 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
32 ms |
82744 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |