Bribing Friends

Observations

The most important observation is that if we have selected a subset of the cows to bribe, it is always optimal to use ice cream cones in order of X_i (number of ice cream cones per moonie traded), until we exhaust all our ice cream cones. This means that in each DP step we will either have zero moonies or B ice cream cones, which means that we can essentially reduce this to knapsack DP, with time complexity O(N * (A+B)).

Pseudocode

sort cows by X_i
dp[i][j] = N+1 by A+B+1 matrix // dp[i][j] = max popularity with i cows and j moonies+ice cream cones
for i from 1 to N
    for j from 1 to A+B
        m = number of moonies in j
        if we can bribe this cow
            if m >= C_i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - m] + P_i)
            else
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - (m + (C_i - m) * X_i)] + P_i)
output dp[N][A+B]

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    // input
    int n, a, b;
    cin >> n >> a >> b;

    vector<vector<int>> c(n, vector<int>(3));
    for (int i=0; i<n; i++) {
        cin >> c[i][0] >> c[i][1] >> c[i][2];
    }
    sort(c.begin(), c.end(),
        [](const vector<int> & x, const vector<int> & y) {
            return x[2] < y[2];
        }
    );

    // dp[j] = max popularity with max(0, j-b) moonies and min(b, j) ice creams
    vector<int> dp(a+b+1, 0);
    for (int i=1; i<n+1; i++) {
        for (int j=a+b; j>0; j--) {
            // calculate how many moonies + icecream we need to spend to bribe
            // use moonies first
            int m = max(0, j-b);
            int ic = min(b, j) / c[i-1][2];

            // we can bribe this cow
            if (m + ic >= c[i-1][1]) {
                // we have enough moonies
                if (m >= c[i-1][1]) {
                    dp[j] = max(dp[j], dp[j-c[i-1][1]] + c[i-1][0]);
                }
                // we'll need ice cream cones
                else {
                    dp[j] = max(dp[j], dp[j - (m + (c[i-1][1] - m) * c[i-1][2])] + c[i-1][0]);
                }
            }
        }
    }
    // output
    cout << dp[a+b] << endl;
}