제출 #1134289

#제출 시각아이디문제언어결과실행 시간메모리
1134289MuhammetBank (IZhO14_bank)C++17
71 / 100
1095 ms632 KiB
#include "bits/stdc++.h"

using namespace std;

int n, m, k;

vector <int> a, b, c, v;

map <pair<int,int>, bool> dp;

void f1(int x, int ind, int y){
	if(x < 0) return;
	if(ind == m){
		if(x == 0) v.push_back(y);
		return;
	}
	if((y>>ind)&1){
		f1(x,ind+1,y);
		return;
	}
	f1(x-b[ind+1],ind+1,y|(1<<ind));
	f1(x,ind+1,y);
}

bool f(int x){
	if(x == n+1) return true;
	if(dp.find({x,k}) != dp.end()) return false;
	v.clear();
	f1(a[x],0,k);
	vector <int> v1 = v;
	for(auto i : v1){
		k = i;
		if(f(x+1)) return true;
	}
	dp[{x,k}] = false;
	return false;
}

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

	cin >> n >> m;
	a.resize(n+1), b.resize(m+1), c.resize(m+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= m; i++){
		cin >> b[i];
	}
	cout << (!f(1) ? "NO\n" : "YES\n");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...