Submission #738476

#TimeUsernameProblemLanguageResultExecution timeMemory
738476MODDIBank (IZhO14_bank)C++14
100 / 100
418 ms28356 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m;
vi banknotes, salary;
bool check_bit(int n, int bit){
	int ok = n & (1 << bit);
	if(ok)	return true;
	return false;
}
int set_bit(int n, int b){
	return (n | (1 << b));
}
bool can[21][1001], dp[2][1001][(1<<14)];
int main(){
	cin>>n>>m;
	banknotes.resize(m);
	salary.resize(n);
	for(int i = 0; i < n; i++)	cin>>salary[i];
	for(int i = 0; i < m; i++)	cin>>banknotes[i];
	vector<int> ways[1101];
	for(int j = 0; j < (1 << m); j++){
		int sum = 0;
		for(int bit = 0; bit < m; bit++){
			if(check_bit(j, bit))	sum += banknotes[bit];
		}
		if(sum <= 1000)
			ways[sum].pb(j);
	}
	bool dp[21][(1<<m)];
	memset(dp, false, sizeof dp);
	dp[0][0] = true;
	for(int i = 0; i < n; i++){
		for(int mask = 0; mask < (1 << m); mask++){
			if(!dp[i][mask])	continue;
			for(auto sum_mask : ways[salary[i]]){
				if(mask & sum_mask)	continue;
				dp[i+1][mask | sum_mask] = true;
			}
		}
	}
	for(int j = 0; j < (1 << m); j++){
		if(dp[n][j]){
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...