제출 #1119507

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1119507		hamzabc	은행 (IZhO14_bank)	C++14	0 / 100	1 ms	852 KiB

bank

#include <bits/stdc++.h>
 
 
using namespace std;
 
 
#define all(x) x.begin(), x.end()
#define mod 1000000007
#define sp << " " <<
#define endl << '\n'


long long int N, M;
vector<int> people;
vector<int> banknotes;
vector<vector<int>> memoization;


int dp(int n, long long int mask);


inline int calldp(int n, long long int mask, int need, int opt = M - 1){
	if (need == 0)
		return dp(n, mask);
	for (int i = opt; i >= 0 && banknotes[i] >= need / 2; i--){
		if (mask & (1 << i))
			continue;
		if (calldp(n, mask | (1 << i), need - banknotes[i], i - 1))
			return 1;
	}
	return 0;
}


int dp(int n, long long int mask){
	if (n == N)
		return 1;
	if (memoization[n][mask] != -1)
		return memoization[n][mask];
	memoization[n][mask] = calldp(n + 1, mask, people[n]);
	return memoization[n][mask];
}


signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	people.resize(N);
	banknotes.resize(M);
	memoization.resize(N, vector<int>(1 << M, -1));
	for (int i = 0; i < N; i++)
		cin >> people[i];
	for (int o = 0; o < M; o++)
		cin >> banknotes[o];
	sort(all(banknotes));
	if (dp(0, 0)){
		cout << "YES";
	}else
		cout << "NO";
	return 0;
}

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