제출 #1194201

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194201		PlayVoltz	Bank (IZhO14_bank)	C++20	71 / 100	1095 ms	788 KiB

bank

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

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;
}

int 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<(1<<m); ++i){
		int sum = 0;
		for (int j=0; j<=m; ++j){
			if (i&(1<<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