Define $\text{dp}[i][j][k]$ to be the maximum amount of popularity Bessie can achieve with her friends $1 \ldots i$, $j$ moonies, and $k$ ice cream cones.

• If Bessie does not want to bribe cow $i$, then we can update $\text{dp}[i+1][j][k] = \text{dp}[i][j][k]$.
• If Bessie chooses to bribe cow $i$, she can optionally spend some ice cream cones to decrease her cost. Loop through $0 \ldots k$ to brute force how many ice cream cones Bessie will spend on cow $i$. If Bessie chooses to spend $c$ cones, then Bessie needs to spend $C_i - \lfloor \frac{c}{X_i} \rfloor$ moonies. Therefore, $\text{dp}[i + 1][j - (C_i - \lfloor \frac{c}{X_i} \rfloor)][k - c] = \text{dp}[i][j][k]$.

However, this code runs in $\mathcal{O}(NAB^2)$ time.

To do better, suppose that we already know the set of cows that we plan to take. How do we check that inviting these cows is within our budget? We can do this greedily. Start by not spending any cones at all, and spending only money to invite these cows. This might cost more money than we have. Next, we will try to spend some ice cream cones to reduce the amount of money we need to spend. Note that at this point, we would always choose the cow with the smallest $X_i$ to decrease the total cost most efficiently. In other words, the cows that we bribe with cones is a prefix of all cows when sorted by $X_i$. This observation leads us to the fact that for each $j$ and $k$, to choose a new cow $i$, we only have one transition to consider. Sort Bessie’s friends by increasing $X_i$. Note that if we take cow $i$, we want to spend all our ice cream cones first before we move on to spending money, so we would use $c = \min(k, C_i\cdot X_i)$ cones and $C_i - \lfloor \frac{c}{X_i} \rfloor$ moonies. Due to the $\mathcal{O}(NAB)$ states we have, this results in an $\mathcal{O}(NAB)$ time dp.

We can further remove one dimension. By the same observation from before - that cones are used to the maximum before moonies - for all dp states, either $k$ equals zero or $j$ equals $A$. For each $i$, we now only consider $\mathcal{O}(A + B)$ states, leading us to our final $\mathcal{O}(N(A+B))$ solution.

Timothy's C++ code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2000 + 1;
 
int dp[N][2 * N];
 
void set_max(int &a, int b) {
    if (b > a) a = b;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, moonie, cones;
    cin >> n >> moonie >> cones;
 
    vector<array<int, 3>> cows(n);
    for (auto &[x, p, c] : cows) {
        cin >> p >> c >> x;
    }
    sort(cows.begin(), cows.end());
 
    memset(dp, -1, sizeof dp);
 
    dp[0][moonie + cones] = 0;
    for (int i = 0; i < n; ++i) {
        auto [x, p, c] = cows[i];
        for (int j = 0; j <= moonie + cones; ++j) {
            if (dp[i][j] == -1) continue;
 
            set_max(dp[i + 1][j], dp[i][j]);
            if (j - c * x >= moonie) {
                set_max(dp[i + 1][j - c * x], dp[i][j] + p);
            } else if (j > moonie) {
                int cost_left = c - (j - moonie) / x;
                if (moonie - cost_left >= 0)
                    set_max(dp[i + 1][moonie - cost_left], dp[i][j] + p);
            } else if (j <= moonie && j - c >= 0) {
                set_max(dp[i + 1][j - c], dp[i][j] + p);
            }
        }
    }
 
    cout << *max_element(dp[n], dp[n] + moonie + cones + 1) << "\n";
}

Nick Wu's Python code:

n, a, b = (int(x) for x in input().split())
dpmoney = [0] * (a+1)
dpcones = [0] * (b+1)
v = sorted([[int(x) for x in input().split()] for _ in range(n)], key = lambda x: x[2])
for p, c, x in v:
  for i in range(a-c+1):
    dpmoney[i] = max(dpmoney[i], dpmoney[i+c] + p)
  for i in range(max(0, a-c+1), min(a+1, a-c+1 + (b // x))):
    conesneed = (i-(a-c)) * x
    dpmoney[i] = max(dpmoney[i], dpcones[conesneed] + p)
  for i in range(b-x*c+1):
    dpcones[i] = max(dpcones[i], dpcones[i+x*c] + p)
    dpmoney[a] = max(dpmoney[a], dpcones[i])
print(dpmoney[0])