Submission #614838

#TimeUsernameProblemLanguageResultExecution timeMemory
614838jophyyjhJelly Flavours (IOI20_jelly)C++14
100 / 100
194 ms684 KiB
/** * 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 jelly_t { int a, b; }; 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<jelly_t> values(n); for (int i = 0; i < n; i++) values[i].a = a[i], values[i].b = b[i]; std::sort(values.begin(), values.end(), [](const jelly_t& j1, const jelly_t& j2) { return j1.a < j2.a; }); 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 >= values[k - 1].a) dp[k % 2][t].max_f++, dp[k % 2][t].money_A -= values[k - 1].a; if (t >= values[k - 1].b) { choice_t c = dp[(k - 1) % 2][t - values[k - 1].b]; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...