제출 #436101

#제출 시각아이디문제언어결과실행 시간메모리
436101zeyu은행 (IZhO14_bank)C++17
100 / 100
128 ms8640 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...