| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1153074 | MrDeboo | 은행 (IZhO14_bank) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define mod 998244353
#define int long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>;
vector<int>bt(1<<21);
vector<int>eq(1<<21,-1);
vector<int>eqq(1<<21,-1);
int n,m;
vector<int>v(n),vv(m);
void pee(int sm=0,int sl=0){
if(eqq[sl]!=-1)return;
eqq[sl]=sm;
for(int i=0;i<m;i++){
if((1<<i)&sl);
else pee(sm+vv[i],(sl|(1<<i)));
}
}
void pre(int sm=0,int sl=0){
if(eq[sl]!=-1)return;
eq[sl]=sm;
for(int i=0;i<n;i++){
if((1<<i)&sl);
else pre(sm+v[i],(sl|(1<<i)));
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
v.resize(n);
vv.resize(m);
for(auto &i:v)cin>>i;
for(auto &i:vv)cin>>i;
sort(v.begin(),v.end(),greater<int>());
for(int i=1;i<n;i++)assert(arr[i]!=arr[i-1]);
pre();
pee();
for(int i=1;i<(1<<m);i++){
for(int w=i;w;w=(w-1)&i){
int ww=(w^i);
int b=(bt[w]|bt[ww]),a=eqq[i]-eq[b];
// if(i==1)cout<<a<<endl;
for(int j=0;j<n;j++){
if(((b&(1<<j))==0)&&v[j]==a){
a-=v[j];
b|=(1<<j);
}
}
if(__builtin_popcount(b)>__builtin_popcount(bt[i])){
// cout<<i<<' '<<w<<' '<<b<<' '<<__builtin_popcount(b)<<' '<<a<<endl;
bt[i]=b;
}
}
}
cout<<(__builtin_popcount(bt[(1<<m)-1])==n?"YES":"NO");
}