Submission #1056561

#TimeUsernameProblemLanguageResultExecution timeMemory
1056561vjudge1은행 (IZhO14_bank)C++14
100 / 100
70 ms10872 KiB
#include <bits/stdc++.h>
#define ii pair<int,int>
#define fi first
#define se second
using namespace std;

const int N = 21;
int n, m, a[N], b[N];
ii dp[1<<N];
bool vst[1<<N];

int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 0; i < m; i++) cin >> b[i];

	vst[0] = 1;
	dp[0] = {1, 0}; 
	for(int mask = 1; mask < (1 << m); mask++){
		for(int j = 0; j < m; j++){
			if(mask & (1 << j) && vst[mask ^ (1 << j)]){
				ii tmp = dp[mask ^ (1 << j)];
				tmp.se += b[j];
				if(tmp.se < a[tmp.fi]){
					vst[mask] = 1;
					dp[mask] = tmp;
				} else if(tmp.se == a[tmp.fi]){
					vst[mask] = 1;
                    dp[mask] = {tmp.fi + 1 , 0};
				}
			}
		}
	}
	for(int mask = 1; mask < (1 << m); mask++){
		if(dp[mask].fi > n){
			cout << "YES";
			return 0;
		}
	}
	cout << "NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...