Submission #1194202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194202		PlayVoltz	Bank (IZhO14_bank)	C++20	71 / 100	1096 ms	604 KiB

bank

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

#define int long long
int n, m;
vector <int> ppl;
vector <int> notes;
unordered_map<int, bool> exist;
unordered_map<int, vector<int> > masks;

bool can(int index, int mask){
	if (index==n-1){
		return true;
	}
	for (auto num:masks[ppl[index+1]]){
		if ((mask&num)==0){
			if (can(index+1, mask+num))return true;
		}
	}
	return false;
}

int32_t main(){
	cin>>n>>m;
	ppl.resize(n);
	notes.resize(m);
	for (int i=0; i<n; ++i){
		cin>>ppl[i];
		exist[ppl[i]] = true;
	}
	for (int i=0; i<m; ++i){
		cin>>notes[i];
	}
	for (int i=0; i<(1ll<<m); ++i){
		int sum = 0;
		for (int j=0; j<=m; ++j){
			if (i&(1ll<<j)){
				sum+=notes[j];
			}
		}
		if (exist[sum]){
			masks[sum].push_back(i);
		}
	}
	if (can(-1, 0))cout<<"YES";
	else cout<<"NO";
}

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