Overview

For each gem, you choose one of three options: “don’t bring it,” “bring it at normal weight,” or “bring it using a weight-reduction case.” The goal is to maximize the total value while keeping the total weight at most \(C\).

This can be solved with a 0/1 knapsack DP that also tracks the number of weight-reduction cases used.

Analysis

Each gem can be brought at most once. Additionally, even when using weight-reduction cases, you cannot use multiple cases on the same gem.

For gem \(i\), there are the following 3 choices:

1. Don’t bring it
2. Bring it at normal weight \(W_i\)
3. Use 1 weight-reduction case and bring it at weight \(\lfloor W_i / 2 \rfloor\)

If we naively try all combinations, each gem has up to 3 choices, resulting in an enormous computation of \(O(3^N)\), which is far too slow for \(N \leq 10^5\).

In a standard 0/1 knapsack, we only track “current weight” as the state, but in this problem there is an upper limit \(K\) on the number of weight-reduction cases that can be used.
Therefore, in addition to “weight,” we also need to manage “how many cases have been used” as a DP state.

Thus, we consider the following DP:

\(dp[k][w] =\) the maximum value when exactly \(k\) weight-reduction cases are used and the total weight is exactly \(w\)

Unreachable states are initialized with a sufficiently small value.

We process gems one by one, and for each gem, perform transitions for:

• Adding it at normal weight
• Adding it with weight reduction

Algorithm

Define the DP array as follows:

\[ dp[k][w] = \text{the maximum value when } k \text{ weight-reduction cases are used and the total weight is } w \]

The initial state represents selecting nothing:

\[ dp[0][0] = 0 \]

All other states are unreachable and initialized with a sufficiently small value.

For each gem \((B_i, W_i)\), the weight after reduction is:

\[ \left\lfloor \frac{W_i}{2} \right\rfloor \]

When the current state is \(dp[k][w]\), we perform the following transitions:

1. Bring at normal weight

The weight increases by \(W_i\) and the value increases by \(B_i\).

\[ dp[k][w + W_i] = \max(dp[k][w + W_i], dp[k][w] + B_i) \]

This applies only when \(w + W_i \leq C\).

2. Bring using a weight-reduction case

One case is used, the weight increases by \(\lfloor W_i / 2 \rfloor\), and the value increases by \(B_i\).

\[ dp[k + 1][w + \lfloor W_i / 2 \rfloor] = \max(dp[k + 1][w + \lfloor W_i / 2 \rfloor], dp[k][w] + B_i) \]

This applies only when \(k + 1 \leq K\) and \(w + \lfloor W_i / 2 \rfloor \leq C\).

Reason for iterating in reverse order

Each gem can be selected at most once.

Therefore, to prevent the same gem from being used multiple times during the DP update, we iterate \(k\) and \(w\) in reverse order from large to small.

for (int k = K; k >= 0; k--) {
    for (int w = C; w >= 0; w--) {
        ...
    }
}

This prevents a state updated by the current gem from being used again during the processing of the same gem.

Finally, since the weight only needs to be at most \(C\) and at most \(K\) cases can be used, the answer is the maximum over all \(dp[k][w]\).

\[ \max_{0 \leq k \leq K,\ 0 \leq w \leq C} dp[k][w] \]

Complexity

• Time complexity: \(O(NKC)\)
• Space complexity: \(O(KC)\)

Since the constraints guarantee

\[ N(K+1)(C+1) \leq 2 \times 10^7 \]

this complexity is sufficient.

Implementation Notes

The DP values represent total value, which can become quite large.
Since \(B_i \leq 10^9\) and \(N\) can be large, use long long instead of int.

Also, prepare a sufficiently small value NEG to represent unreachable states.

const long long NEG = -(1LL << 60);

Before performing a transition, check whether the state is reachable.

if (dp[k][w] == NEG) continue;

Finally, it is not necessary to use exactly \(K\) cases, nor is it necessary for the weight to be exactly \(C\).
Therefore, we need to take the maximum over all \(k \leq K\) and \(w \leq C\).

Source Code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, C, K;
    cin >> N >> C >> K;

    const long long NEG = -(1LL << 60);
    vector<vector<long long>> dp(K + 1, vector<long long>(C + 1, NEG));
    dp[0][0] = 0;

    for (int i = 0; i < N; i++) {
        long long B;
        int W;
        cin >> B >> W;

        int halfW = W / 2;

        for (int k = K; k >= 0; k--) {
            for (int w = C; w >= 0; w--) {
                if (dp[k][w] == NEG) continue;

                if (w + W <= C) {
                    dp[k][w + W] = max(dp[k][w + W], dp[k][w] + B);
                }

                if (k + 1 <= K && w + halfW <= C) {
                    dp[k + 1][w + halfW] = max(dp[k + 1][w + halfW], dp[k][w] + B);
                }
            }
        }
    }

    long long ans = 0;
    for (int k = 0; k <= K; k++) {
        for (int w = 0; w <= C; w++) {
            ans = max(ans, dp[k][w]);
        }
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.