제출 #318385

#제출 시각아이디문제언어결과실행 시간메모리
318385Gurban은행 (IZhO14_bank)C++17
71 / 100
1091 ms13028 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn=22;
const int N = 1<<maxn;
int n,m,a[maxn],b[maxn],sum[N],p[maxn];
bool can[maxn][N],dp[maxn][N];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> a[i],p[i]=p[i-1]+a[i];
	for(int i = 0;i < m;i++) cin >> b[i];

	for(int i = 0;i < (1<<m);i++)
		for(int j = 0;j < m;j++) if(i & (1<<j)) sum[i] += b[j];

	for(int i = 0;i < (1<<m);i++) can[0][i] = 1;

	for(int i = 1;i <= n;i++){
		for(int j = 0;j < (1<<m);j++) if(sum[j] == p[i]) can[i][j] = can[i-1][j];
		for(int j = 0;j < (1 << m);j++)
			for(int k = 0;k < m;k++) if((1<<k) & j) if(can[i][j-(1<<k)] == 1) can[i][j]=1;
	}
	
	// for(int i = 1;i <= n;i++){
	// 	cout<<i<<" ---> ";
	// 	for(int j = 0;j < (1<<m);j++) if(can[i][j] == 1) cout<<j<<' ';
	// 	cout<<'\n';
	// }

	if(can[n][(1<<m) - 1]) cout<<"YES";
	else cout<<"NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...