#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
/// order_of_key return number of elements less than x.
/// find_by_order return index.
const int N = 3*1e5 + 10;
const int M = 998244353;
#define ll long long int
#define ld long double
#define rep(i, n) for (ll i = 0; i < n; i++)
#define ff first
#define ss second
#define rep1(i, n) for (ll i = 1; i < n; i++)
#define repr(i, n) for (ll i = n - 1; i >= 0; i--)
#define pb push_back
#define vi vector<int>
#define vll vector<long long>
#define vpll vector<pair<ll, ll>>
#define vvll vector<vector<ll>>
#define vvpll vector<vector<pll>>
#define pll pair<ll, ll>
const ll INF = 1e9+7;
ll binmult(int a, int b)
{
ll ans = 0;
while (b > 0)
{
if (b & 1)
ans = (ans + a) % M;
a = (a + a) % M;
b >>= 1;
}
return ans;
}
ll binpow(int a, int b)
{
ll ans = 1;
while (b > 0)
{
if (b & 1)
ans = binmult(ans, a);
a = binmult(a, a);
b >>= 1;
}
return ans;
}
ll bs_sqrt(ll x)
{
ll left = 0, right = 2000000123;
while (right > left)
{
ll mid = (left + right) / 2;
if (mid * mid > x)
right = mid;
else
left = mid + 1;
}
return left - 1;
}
ll inverse(ll x,ll M){
ll y=binmult(x,M-2);
return y;
}
// ll nCr(ll n, ll r)
// {
// return ((fac(n)*inverse(fac(n-r)))%M*inverse(fac(r)))%M;
// }
//----------------------------------------------------------------------
// DSU
// vll par(N+1,0),sz(N+1,0);
// void make(int x){
// par[x]=x;sz[x]=1;
// }
// int find(int x){
// if(x==par[x]) return x;
// return par[x]=find(par[x]);
// }
// void Union(int b,int a){
// a=find(a),b=find(b);
// // if(a!=b)
// {
// if(sz[a]<sz[b]) swap(a,b);
// sz[a]+=sz[b];
// par[b]=a;
// }
// }
//--------------------------------------------------------------------
// Dynamic Range Minimum Segment Tree
// vll a(N), seg(4*N);
// void build(int ind, int low, int high){
// if(low==high) {seg[ind]=a[low]; return ;}
// ll mid=(high+low)/2;
// build(2*ind+1, low, mid);
// build(2*ind+2, mid+1,high);
// seg[ind]=min(seg[2*ind+1], seg[2*ind+2]);
// }
// void update(ll ind, ll low,ll high, ll i, ll val){
// if(low==high ){
// if(low==i)
// seg[ind]=val;
// return ;
// }
// if(i<low || i>high) return ;
// ll mid=(high+low)/2;
// update(2*ind+1,low, mid, i, val);
// update(2*ind+2,mid+1, high, i, val);
// seg[ind]=min(seg[2*ind+1], seg[2*ind+2]);
// return ;
// }
// ll query(ll ind, ll low,ll high, ll l, ll r){
// if(l<=low && high<=r) return seg[ind];
// if(high< l || low>r) return INT_MAX;
// ll mid=(high+low)/2;
// return min(query(2*ind+1, low, mid, l, r), query(2*ind+2, mid+1, high, l, r));
// }
//-----------------------------------------------------------------------
// void dfs(ll i,ll s,vvll &g, vll &dis,vvll &dp){
// ll ans=dis[i];
// for(auto it: g[i]){
// if(dp[i][s]==INF) {
// if(dis[it] > dis[i])
// { dfs(it,s,g,dis,dp);
// ans=min(ans, dp[it][s]);
// }
// else{
// if(s==0)
// {dfs(it,1,g,dis,dp);
// ans=min(ans, dp[it][1]);}
// }
// }
// else{
// if(dis[it] > dis[i])
// ans=min(ans, dp[it][s]);
// if(s==0 && dis[it] <= dis[i]) ans=min(ans, dp[it][1]);
// }
// }
// dp[i][s]=ans;
// }
void bfs(vvll &g, vll &vis, vll &dis, ll w, ll s){
queue<pll> q;
q.push({0,s});
// dis[1]=0;
while(!q.empty()){
pll cur=q.front(); q.pop();
if(vis[cur.ss]) continue;
vis[cur.ss]=1;
for(auto it:g[cur.ss]){
if(cur.ff+ 1 < dis[it])
dis[it]=cur.ff+1; q.push({dis[it],it});
}
}
rep(i,dis.size()) dis[i]=w*dis[i];
}
void solve(){
ll n,m;cin>>n>>m;
vll a(n), b(m);
rep(i,n) cin>>a[i];
rep(i,m) cin>>b[i];
vvll mp(n);
rep(i,(1<<m)){
ll s=0;
rep(j,m){
if((i>>j)&1){
s+=b[j];
}
}
ll ind=find(a.begin(), a.end(), s)-a.begin();
if(ind!=n)
{
mp[ind].pb(i);
}
}
vvll dp(n+1,vll((1<<m)+1,0));
for(auto it : mp[0]) {dp[0][it]=1; }
// cout<<it<<" ";}
// cout<<endl;
rep1(i,n){
rep(j,(1<<m)){
for(auto it: mp[i]){
if((it&j)!=it) continue;
dp[i][j]|=dp[i-1][j^it];
}
}
}
ll ok=0;
rep(j,1<<m){
if(dp[n-1][j]==1) {
// cout<<j<<" ";
ok=1;
}
}
if(ok) cout<<"YES\n";
else cout<<"NO\n";
}
int main()
{
// freopen("pails.in", "r", stdin);
// freopen("pails.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t=1;
// cin >> t;
ll tt = 1;
ll p=1;
while (t--)
{
solve();
tt++;
}
return 0;
}
/*
to get the maxsum, and minsum of a array from start but processing from end:-
suppose s is the array, sul - suffix_minsum, sur - suffix_maxsum
for (int i = n - 1; i >= 0; --i){
int d = s[i];
sul.push_back(min(0, sul.back() + d));
sur.push_back(max(0, sur.back() + d));
}
*/
Compilation message
bank.cpp: In function 'void bfs(std::vector<std::vector<long long int> >&, std::vector<long long int>&, std::vector<long long int>&, long long int, long long int)':
bank.cpp:163:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
163 | if(cur.ff+ 1 < dis[it])
| ^~
bank.cpp:164:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
164 | dis[it]=cur.ff+1; q.push({dis[it],it});
| ^
bank.cpp:17:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | #define rep(i, n) for (ll i = 0; i < n; i++)
......
167 | rep(i,dis.size()) dis[i]=w*dis[i];
| ~~~~~~~~~~~~
bank.cpp:167:5: note: in expansion of macro 'rep'
167 | rep(i,dis.size()) dis[i]=w*dis[i];
| ^~~
bank.cpp: In function 'int main()':
bank.cpp:225:12: warning: unused variable 'p' [-Wunused-variable]
225 | ll p=1;
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
73 ms |
25004 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
72 ms |
25128 KB |
Output is correct |
| 9 |
Correct |
80 ms |
25172 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1884 KB |
Output is correct |
| 4 |
Correct |
3 ms |
2504 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1884 KB |
Output is correct |
| 6 |
Correct |
2 ms |
1372 KB |
Output is correct |
| 7 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 8 |
Correct |
2 ms |
904 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1880 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1628 KB |
Output is correct |
| 11 |
Correct |
3 ms |
2396 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
73 ms |
25004 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
72 ms |
25128 KB |
Output is correct |
| 9 |
Correct |
80 ms |
25172 KB |
Output is correct |
| 10 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
