Submission #738467

#	Time	Username	Problem	Language	Result	Execution time	Memory
738467		MODDI	Bank (IZhO14_bank)	C++14	19 / 100	91 ms	262144 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];
bool dp[21][1001][(1<<14)];
bool f(int at, int sum, int mask){
	if(sum > salary[at])	return false;
	if(at >= n)	return true;
	if(dp[at][sum][mask])	return true;
	if(sum == salary[at]){
		bool ans = f(at+1, 0, mask);
		return dp[at][sum][mask] = ans;
	}
	else{
		bool ans = false;
		for(int i = 0; i < m; i++){
			if(!check_bit(mask, i)){
				int new_mask = set_bit(mask, i);
				ans |= f(at, sum + banknotes[i], new_mask);
			}
		}
		return dp[at][sum][mask] = ans;
	}
}
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];
	sort(salary.begin(), salary.end());
	if(n == 1){
		memset(can, false, sizeof can);
		can[0][0] = can[0][banknotes[0]] = true;
		for(int i = 1; i < m; i++){
			for(int j = 0; j <= 1000; j++){
				can[i][j] |= can[i-1][j];
				if(j >= banknotes[i])
					can[i][j] |= can[i-1][j-banknotes[i]];
			}
		}
		if(can[m-1][salary[0]])	cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	else if(m <= 14){
		memset(dp, false, sizeof dp);
		bool ans = f(0, 0, 0);
		if(ans)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
	else
		cout<<"NO"<<endl; //TODO
	return 0;
}

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