이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |