/**
* A really nice dp + greedy problem~ I can recall that this is one the first few IOI
* problems I ever saw, and I also heard the solution from tinjyu.
*
* Anyway, the first few subtasks are pretty easy. In particular, when there's only
* one person (e.g. when y=0) we can simply sort all flavours according to price (for
* that person) and greedily pick from the small ones. From the constraints, one may
* guess that the only way to AC this problem is to do a O(nx) dp (not a O(nxy) one).
* Now, let dp[i][t] be the dp state when we only consider the first i flavours and
* exactly t dollars are spent on store B. Each dp state already captures the cost in
* B, so it may (?!) natural to maximize the num of unique flavours she can buy while
* minimizing the amount of money spent on store A.
* So, we first SORT the flavours based on their price in store A (from small to
* large). We know that if we've selected a subset of jelly in B, she would just
* greedily pick the remaining ones in store A (from left to right). Therefore, in
* each dp state, we store the max num of flavours we can buy. In addition, among all
* choices that can reach the max. num of flavours, we store the max amount of money
* that can be left with in store A. It's not difficult to prove that this is indeed
* a valid approach using greedy arguments. Nice problem!
*
* Time Complexity: O(ny) (or equivalently, O(nx))
* Implementation 1
*/
#include <bits/stdc++.h>
#include "jelly.h"
typedef std::vector<int> vec;
const int INF = 0x3f3f3f3f;
struct choice_t {
int max_f, money_A;
};
inline bool operator<(const choice_t& c1, const choice_t& c2) {
return c1.max_f < c2.max_f || (c1.max_f == c2.max_f && c1.money_A < c2.money_A);
}
int find_maximum_unique(int x, int y, vec a, vec b) {
int n = a.size();
std::vector<std::vector<choice_t>> dp(2, std::vector<choice_t>(y + 1));
dp[0][0] = choice_t{0, x};
for (int t = 1; t <= y; t++)
dp[0][t] = choice_t{-INF, -INF};
int ans = 0;
for (int k = 1; k <= n; k++) {
for (int t = 0; t <= y; t++) {
dp[k % 2][t] = dp[(k - 1) % 2][t];
if (dp[k % 2][t].money_A >= a[k - 1])
dp[k % 2][t].max_f++, dp[k % 2][t].money_A -= a[k - 1];
if (t >= b[k - 1]) {
choice_t c = dp[(k - 1) % 2][t - b[k - 1]];
c.max_f++;
dp[k % 2][t] = std::max(dp[k % 2][t], c);
}
ans = std::max(ans, dp[k % 2][t].max_f);
}
}
return ans;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '7', found: '6' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '7', found: '6' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
1st lines differ - on the 1st token, expected: '689', found: '648' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
340 KB |
1st lines differ - on the 1st token, expected: '62', found: '12' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
468 KB |
1st lines differ - on the 1st token, expected: '154', found: '63' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
1st lines differ - on the 1st token, expected: '7', found: '6' |
| 3 |
Halted |
0 ms |
0 KB |
- |
