Submission #1313329

#TimeUsernameProblemLanguageResultExecution timeMemory
1313329aicloBank (IZhO14_bank)C++20
100 / 100
354 ms12600 KiB
#include <bits/stdc++.h>
using namespace std;

int sum[1 << 20];
int a[20], b[20];
int n, m;

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

}

void precompute(){
	for(int mask = 0; mask < (1 << m); mask++)
		for(int i = 0; i < m; i++)
			if(mask & (1 << i)) sum[mask] += b[i];
}

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	wczytaj();	
	precompute();
	
	vector<bool> DP(1<<m);
	DP[0] = 1;
	
	unordered_map<int, vector<int>> sums;
	for(int mask = 0; mask < (1 << m); mask++) sums[sum[mask]].push_back(mask);
	
	for(int i = 0; i < n; i++){
		vector<bool> tmp(1<<m);
		for(int mask = 0; mask < (1 << m); mask++){
			if(!DP[mask]) continue;
			for(int submask: sums[a[i]]){
				if((submask & mask) == 0) tmp[mask | submask] = 1;
			}
		}
		DP = tmp;
	}
	
	for(int mask = 0; mask < (1 << m); mask++)
		if(DP[mask]){
			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...