제출 #436101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
436101		zeyu	은행 (IZhO14_bank)	C++17	100 / 100	128 ms	8640 KiB

bank

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n, m;
	cin >> n >> m;
	vector<int> s(n), p(m);
	for (int i = 0; i < n; i ++) cin >> s[i];
	for (int i = 0; i < m; i ++) cin >> p[i];
	vector<int> dp(1 << m, -1), left(1 << m);
	dp[0] = 0;
	bool ok = false;
	for (int i = 0; i < 1 << m; i ++){
		if (dp[i] == n) {
			ok = true;
			break;
		}
		if (dp[i] == -1) continue;
		for (int j = 0; j < m; j ++){
			if (! (i & (1 << j))){
				int to = i | (1 << j);
				if (left[i] + p[j] == s[dp[i]]) {
					dp[to] = dp[i] + 1;
					left[to] = 0;
				} else if (left[i] + p[j] < s[dp[i]]){
					dp[to] = dp[i];
					left[to] = left[i] + p[j];
				}
			}
		}
	}
	if (ok) cout << "YES" << endl;
	else cout << "NO" << endl;
}

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