Submission #615860

#	Time	Username	Problem	Language	Result	Execution time	Memory
615860		jophyyjh	Jelly Flavours (IOI20_jelly)	C++14	100 / 100	256 ms	154908 KiB

jelly

/**
 * 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!
 * 
 * Impl2 is inspired by https://codeforces.com/blog/entry/91804 and
 * https://codeforces.com/blog/entry/82625. Basically, we split the array into two
 * sections where the last element in the 1st section is the last item we buy in
 * store A. We use dp to compute the smallest cost used in the 1st part, and use dp
 * again to compute the num of flavours in 2nd part. The idea is to split the items
 * into two parts AND also split our money into two.
 * 
 * Time Complexity: O(ny)       (or equivalently, O(nx))
 * Implementation 2
*/
 
#include <bits/stdc++.h>
#include "jelly.h"
 
typedef std::vector<int>	vec;
 
const int INF = 0x3f3f3f3f;
 
 
struct jelly_t {
    int a, b;
};
 
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.b < j2.b;
              });
    
    // dp1[i][t] = using exactly t dollars in store A, the min amount of money needed
    //             to be spent on store B if we're to buy all the first i products. 
    std::vector<vec> dp1(n + 1, vec(x + 1));
    dp1[0][0] = 0;
    for (int t = 1; t <= x; t++)
        dp1[0][t] = INF;
    for (int k = 0; k < n; k++) {
        for (int t = 0; t <= x; t++) {
            dp1[k + 1][t] = dp1[k][t] + values[k].b;
            if (t >= values[k].a)
                dp1[k + 1][t] = std::min(dp1[k + 1][t], dp1[k][t - values[k].a]);
        }
    }
    // dp2[i][t] = max num of flavours we can buy, with t dollars in store A.
    std::vector<vec> dp2(n + 2, vec(x + 1));
    dp2[n + 1][0] = 0;
    for (int t = 1; t <= x; t++)
        dp2[n + 1][t] = -INF;
    for (int k = n; k >= 1; k--) {
        for (int t = 0; t <= x; t++) {
            dp2[k][t] = dp2[k + 1][t];
            if (t >= values[k - 1].a)
                dp2[k][t] = std::max(dp2[k][t], dp2[k + 1][t - values[k - 1].a] + 1);
        }
    }
    // exactly -> at most
    for (int k = 0; k <= n; k++) {
        for (int t = 1; t <= x; t++)
            dp1[k][t] = std::min(dp1[k][t], dp1[k][t - 1]);
    }
    int ans = 0;
    for (int k = 0; k <= n; k++) {
        for (int t = 0; t <= x; t++) {
            if (dp1[k][t] <= y)
                ans = std::max(ans, k + dp2[k + 1][x - t]);
        }
    }
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 14 / 14
• Subtask 6: 32 / 32