제출 #656383

#제출 시각아이디문제언어결과실행 시간메모리
656383boykut은행 (IZhO14_bank)C++14
100 / 100
430 ms54820 KiB
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const int N = 22;
int a[N], b[N], dp[N][1<<N], n, m;
vector<int> can[1001];
 
int main() {
	cin.tie()->sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	int mx = *max_element(a, a+n);
	for (int mask = 0; mask < (1<<m); mask++) {
		int s = 0;
		for (int i = 0; i < m; i++) {
			if (((mask>>i)&1)) s += b[i];
		}
		if (s <= mx)
			can[s].push_back(mask);
	}
	
	for (int mask : can[a[0]])
		dp[0][mask] = 1;
		
	for (int i = 1; i < n; i++) {
		for (int mask = 0; mask < (1<<m); mask++) {
			if (dp[i-1][mask] == 0) continue;
			for (int p : can[a[i]]) {
				if ((mask & p) == 0) {
					dp[i][mask | p] |= dp[i-1][mask];
				}
			}
		}
	}
	for (int mask = 0; mask < (1<<m); mask++) {
		if (dp[n-1][mask] == 1)
			return cout << "YES", 0;
	}
	return cout << "NO", 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...