Submission #1104091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104091		JohnnyVenturas	Bank (IZhO14_bank)	C++17	100 / 100	77 ms	8808 KiB

bank

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

/*
Setting:

i) You are given n salaries
ii) You are given m bills


Rules:
You can yse a bill only once


Question:
Can you form all salaries using the given bills?

Input:
n - [1, 20]
m - [1, 20]

Example 1:
1 5
8
4 2 5 1 3

8 = 5 + 3

How to approach this problem?

First we observe that the size of n and m are relatively small. This suggests an exaustive search for 
a good solution. Trivially we could take all m! permutations of the bills. And then find a way to split 
the permutation into groups, but this would be highly inneficient. We employ a different approach.

Consider for a set of bills the largest prefix of salaries they can make. Let's see what we mean.

1 5
8
4 2 5 1 3

[4  2] -> 0
[4  1 3] -> 1 which is all the salaries


So the problem becomes 
If you can find a prefix of salaries that can be made that is equal with n we can return YES
Otherwise we always return NO.

A state would involve knowing the prefix for a given set. But this is not enough
We also need extendable states. 
Let's say that for a given state S we track the largest prefix we can make and the sum of the remaining values.
Therefore when adding another element to the set, we can always look at the following relation. 

We look what is the largest prefix made, call it i. If i == n we stop
Otherwise to extend the set we need to look if salaries[i] = dp[S].remainder + bills[x] then 
dp[S + x].i = dp[S].i + 1;
dp[S + x].r = 0
else dp[S + x].i = dp[S].i;
dp[S + x].r = dp[S].r + bills[x];

*/


int main() {
	int n, m;	
	cin >> n >> m;

	vector<int> salaries(n), bills(m);

	for(int i = 0; i < n; ++i) {
		cin >> salaries[i];
	}

	for(int i = 0; i < m; ++i) {
		cin >> bills[i];
	}

	vector<pair<int, int>> dp(1 << m, pair<int,int>(0,0));
	for(int s = 0; s < (1 << m); ++s) {
		for(int j = 0; j < m; ++j) {
			if(!((1 << j) & s)) continue;
			int prev_set = s ^ (1 << j);
			int remainder = dp[prev_set].second;
			int i = dp[prev_set].first;

			if(i == n) {
				cout << "YES\n";
				return 0;
			}
			
			if(dp[prev_set] < dp[s]) continue;

			if(salaries[i] == remainder + bills[j]) {
				dp[s].first = i + 1;	
				dp[s].second = 0;
			} else {
				dp[s].first = i;
				dp[s].second = remainder + bills[j];
			}

		}

		if(dp[s].first == n) {
			cout << "YES\n";
			return 0;
		}

	}

	cout << "NO\n";



}

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