| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1189710 | luffy15 | Bank (IZhO14_bank) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
using namespace std;
// Function to check if it's possible to pay exact salaries using available banknotes
bool canPaySalaries(vector<int>& salaries, vector<int>& banknotes, int person, vector<bool>& used) {
if (person == salaries.size()) return true; // All salaries paid
int salary = salaries[person];
// Try each banknote combination that sums to the current salary
for (int i = 0; i < banknotes.size(); i++) {
if (!used[i] && banknotes[i] <= salary) {
if (banknotes[i] == salary) {
used[i] = true;
if (canPaySalaries(salaries, banknotes, person + 1, used)) return true;
used[i] = false;
} else {
// Try to combine with other banknotes
used[i] = true;
if (canPaySalaries(salaries, banknotes, person, used)) return true;
used[i] = false;
}
}
}
return false;
}
int main() {
int N, M;
cin >> N >> M;
vector<int> salaries(N);
for (int i = 0; i < N; i++) {
cin >> salaries[i];
}
vector<int> banknotes(M);
for (int i = 0; i < M; i++) {
cin >> banknotes[i];
}
// If sum of banknotes is less than sum of salaries, it's impossible
long long sum_salaries = 0, sum_banknotes = 0;
for (int s : salaries) sum_salaries += s;
for (int b : banknotes) sum_banknotes += b;
if (sum_banknotes < sum_salaries) {
cout << "NO" << endl;
return 0;
}
// For N=1 case (Subtask 1), check if any combination of banknotes sums to salary
if (N == 1) {
int target = salaries[0];
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int b : banknotes) {
for (int j = target; j >= b; j--) {
dp[j] |= dp[j - b];
}
}
cout << (dp[target] ? "YES" : "NO") << endl;
return 0;
}
// For general case, use backtracking
vector<bool> used(M, false);
cout << (canPaySalaries(salaries, banknotes, 0, used) ? "YES" : "NO") << endl;
return 0;
}