### wOoDeN_sPoOn's blog

By wOoDeN_sPoOn, history, 6 weeks ago,

I was trying to solve jelly from last year(and this year) practice contest. First 4 subtasks are very easy but i don't have any idea about the last 2 subtasks. Can anyone share their solution.

 » 4 weeks ago, # | ← Rev. 2 →   +7 Have you solved the problem by now? If not, here is a hint. Hint 1Let's sort the jelly flavors such that their $a$ values are non-decreasing. We will call a particular way of buying the flavors at stores A and B a solution (each flavor is either bought at store A, store B, or not bought at all). A maximal solution is a solution for which the number of bought flavors is maximal. For a particular solution, let $j$ be the largest index of all flavors that were bought at store A.You can now prove the following statement: There always exists a maximal solution such that all flavors with an index \$ #include "jelly.h" using namespace std; #define ve vector typedef long long ll; typedef pair pii; const int INF = 1e9 + 10; int find_maximum_unique(int x, int y, ve A, ve B) { int n = (int)A.size(); ve> DPA(n + 1, ve(x + 1, INF)); ve> DPB(n + 1, ve(y + 1, INF)); ve F(n); for (int i = 0; i < n; i++) { F[i] = {A[i], B[i]}; } sort(F.begin(), F.end()); DPA[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= x; j++) { int a = j - F[i - 1].first; if (a >= 0) { DPA[i][j] = min(DPA[i][j], DPA[i - 1][a]); } if (DPA[i - 1][j] != INF) { int b = DPA[i - 1][j] + F[i - 1].second; if (b <= y) { DPA[i][j] = min(DPA[i][j], b); } } } } DPB[n] = ve(y + 1, 0); for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= y; j++) { DPB[i][j] = DPB[i + 1][j]; int b = j - F[i].second; if (b >= 0) { DPB[i][j] = max(DPB[i][j], DPB[i + 1][b] + 1); } } } int ans = 0; for (int i = 0; i <= n; i++) { for (int j = 0; j <= x; j++) { int b = DPA[i][j]; if (b != INF) { ans = max(ans, i + DPB[i][y - b]); } } } return ans; }