| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1344914 | aladdin1 | 은행 (IZhO14_bank) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e6 + 25;
int a[N],b[N],dp[N];
int main(){
int n,m;cin>>n>>m;
for (int i=0;i<n;i++) {
cin>>a[i];
if(i>0)a[i]+=a[i-1];
}
for (int i=0;i<m;i++){
cin>>b[i];
}
for(int mask=0;mask<(1<<m);mask++){
if(dp[mask]==n)break;
int sum=a[dp[mask]];
for(int i=0;i<m;i++){
if(mask&(1<<i)){
sum-=b[i];
}
}
for(int i=0;i<m;i++){
if(mask&(1<<i))continue;
dp[mask|(1<<i)]=max(dp[mask|(1<<i)],dp[mask]+(sum==b[i]));
}
}
for(int i=0;i<(1<<m);i++){
if(dp[i]==n){
cout<<"YES";
return;
}
}
cout<<"NO";
}