Submission #738476

#	Time	Username	Problem	Language	Result	Execution time	Memory
738476		MODDI	Bank (IZhO14_bank)	C++14	100 / 100	418 ms	28356 KiB

bank

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

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