| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1184029 | hmms127 | 은행 (IZhO14_bank) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define f1(n) for(int i=0;i<n;i++)
#define f3(n) for(int j=0;j<n;j++)
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define int long long
#define pb push_back
int setbit(int n,int idx,int val){return (val ? ((1LL<<idx)|n):(~(1LL<<idx)&n));}
int getbit(int n,int idx){return ((n>>idx)&1LL);}
int n,a[21],b[21],dp[21][1<<20];
bool rec(int idx,int mak){
if(idx==n)return 1;
int& ret=dp[idx][mak];
if(ret!=-1)return ret;
int newmask=mak;
for(int mask=0;mask<(1<<m);++mask){
vector<int> v;bool valid=true;int sm=0;
for(int i=0;i<m;i++){
if(getbit(mask,i)){
if(getbit(mak,i)){
valid=false;
break;
}
else v.pb(i),sm+=b[i];
}
}
if(valid&&sm==a[idx]){
for(auto it:v)newmask=setbit(newmask,it,1);
if(rec(idx+1,newmask))return ret=true;
//for(auto it:v)newmask=setbit(newmask,it,0);
}
}
return ret=false;
}
int32_t main()
{
speed;
int tt=1,cnt=1;//cin>>tt;
while(tt--){
//freopen("bank.in","r",stdin);
//freopen("bank.out","w",stdout);
cin>>n>>m;
f1(n)cin>>a[i];f1(m)cin>>b[i];
memset(dp,-1,sizeof dp);
cout<<(rec(0,0) ? "YES":"NO")<<e;
}
}