제출 #943267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
943267		mannshah1211	은행 (IZhO14_bank)	C++14	71 / 100	1008 ms	9556 KiB

bank

/**
 *   author: hashman
 *   created: 
**/
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> a(n), b(m);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	vector<vector<int>> masks(1001);
	for (int i = 0; i < (1 << m); i++) {
		int sum = 0;
		for (int j = 0; j < m; j++) {
			if (i & (1 << j)) sum += b[j];
		}
		if (sum <= 1000) masks[sum].push_back(i);
	}
	vector<bitset<1048576>> dp(21, bitset<1048576>());
	for (int i = 0; i < (1 << m); i++) {
		dp[0][i] = true;
	}
	for (int i = 1; i <= n; i++) {
		for (int mask : masks[a[i - 1]]) {
			for (int j = mask; j < (1 << m); j = (j + 1) | mask) {
				dp[i][j] = dp[i][j] || dp[i - 1][j ^ mask];
			}
		}
	}
	if (dp[n][(1 << m) - 1]) cout << "YES\n";
	else cout << "NO\n";
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29