Overview

This problem is an application of Dynamic Programming (DP), extending the standard knapsack problem with weight capacity \(C\) by adding a special rule: “you can halve the weight of up to \(K\) gems (rounding down).”

---

Analysis

1. Basic Approach (Differences from the Standard Knapsack Problem)

In a standard knapsack problem, the DP table is defined as dp[w] = (maximum value when the total weight is w). However, in this problem, we also need to track “how many weight-reduction cases have been used so far.” Therefore, we add the “number of cases used \(k\)” to the state.

• DP State Definition: \(dp[k][w] = \) “the maximum value when \(k\) cases have been used so far and the total weight of carried gems is \(w\)”

2. Reducing Computation and Memory

If we naively define a 3-dimensional array dp[i][k][w] (where \(i\) represents considering up to the \(i\)-th gem), the space complexity becomes \(O(N K C)\). Given the constraints \(N \le 10^5, C \le 10^5, K \le 30\), this would greatly exceed the memory limit (MLE).

Instead, by updating the DP table in-place (overwriting) while iterating over gems \(i\), we eliminate the dimension for gem index \(i\), reducing the space complexity to \(O(K C)\).

---

Algorithm

1. Table Definition and Initialization

Prepare an array dp of size \((K + 1) \times (C + 1)\). - Initialize all values to \(-1\) (unreachable). - Set the initial state as \(dp[0][0] = 0\) (nothing selected).

2. Array Flattening (Optimization Technique)

Instead of using a 2D array dp[K+1][C+1] directly, we flatten it into a 1D array dp[(K+1) * (C+1)]. This improves memory access locality (cache efficiency) and significantly reduces execution time. The index correspondence is as follows: $\(\text{dp}[k][w] \iff \text{dp}[k \times (C + 1) + w]\)$

3. DP Transitions

For each gem \(i\) (value \(B_i\), weight \(W_i\), halved weight \(H_i = \lfloor W_i / 2 \rfloor\)), update the table.

To avoid selecting the same gem multiple times, the loops for \(k\) and \(w\) must always iterate from larger values (in reverse order).

When \(dp[k][w]\) has a valid value (not \(-1\)), perform the following \(2\) transitions:

1. Select gem \(i\) without using a case When \(w + W_i \le C\): $\(dp[k][w + W_i] = \max(dp[k][w + W_i], dp[k][w] + B_i)\)$

2. Select gem \(i\) using a case (when \(k < K\)) When \(w + H_i \le C\): $\(dp[k+1][w + H_i] = \max(dp[k+1][w + H_i], dp[k][w] + B_i)\)$

4. Pruning (Further Optimization)

Keep track of the maximum total weight max_w of gems considered so far. By limiting the starting point of the inner loop (weight \(w\) loop) to \(\min(C, \text{max\_w})\), we skip unnecessary exploration and achieve constant-factor speedup.

---

Complexity

• Time Complexity: \(O(N \cdot K \cdot \min(C, \text{total weight}))\) In the worst case, this is \(O(NKC)\). Given the problem constraints, \(N(K+1)(C+1) \le 2 \times 10^7\), so it comfortably fits within the time limit. Furthermore, pruning makes the actual execution much faster than this.

• Space Complexity: \(O(K \cdot C)\) The size of the DP table maintained is \((K + 1) \times (C + 1)\). With \(K \le 30, C \le 10^5\), the maximum number of elements is approximately \(3.1 \times 10^6\), which is very lightweight at about 25 MB even when using long long type (8 bytes).

---

Implementation Notes

• Importance of Reverse-Order Loops: When updating the DP table in-place, if we update from smaller \(w\) or \(k\) first, the same gem could be used in multiple transitions (resulting in unbounded knapsack behavior). To prevent this, the loops for \(k\) and \(w\) must always iterate in descending order.

• Overflow Prevention: The value \(B_i\) of each gem can be up to \(10^9\), and the total value of carried gems can reach approximately \(10^{14}\). Therefore, the DP table storing values must use a 64-bit integer type (long long) rather than a 32-bit integer type (int).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, C, K;
    if (!(cin >> N >> C >> K)) return 0;

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

    // dp[k * (C + 1) + w]
    // k: 0..K, w: 0..C
    int stride = C + 1;
    vector<long long> dp((K + 1) * stride, -1);
    dp[0] = 0; // dp[0 * stride + 0] = 0

    int max_w = 0;

    for (int i = 0; i < N; ++i) {
        long long b = B[i];
        int w_val = W[i];
        int half_w = w_val / 2;

        int limit_w = min(C, max_w);

        for (int k = K; k >= 0; --k) {
            int k_stride = k * stride;
            int kp1_stride = (k + 1) * stride;

            for (int w = limit_w; w >= 0; --w) {
                long long val = dp[k_stride + w];
                if (val == -1) continue;

                // ケースなしで追加
                if (w + w_val <= C) {
                    long long& target = dp[k_stride + w + w_val];
                    if (val + b > target) {
                        target = val + b;
                    }
                }
                // ケースありで追加
                if (k + 1 <= K && w + half_w <= C) {
                    long long& target = dp[kp1_stride + w + half_w];
                    if (val + b > target) {
                        target = val + b;
                    }
                }
            }
        }
        max_w = min(C, max_w + w_val);
    }

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

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.