Overview

This problem is an extension of the well-known “0-1 Knapsack Problem” with the additional condition that “you can use up to \(K\) weight-reduction cases that halve the weight.” By using dynamic programming (DP) that manages the number of cases used and the current total weight as states, we can find the optimal solution within the time limit.

Analysis

1. Basic Approach (Similarity to the 0-1 Knapsack Problem)

If no weight-reduction cases exist (\(K = 0\)), this problem is exactly the standard “0-1 Knapsack Problem.” In the standard knapsack problem, we define a DP table as follows: - dp[w] = maximum value when the total weight is w

In this problem, we also need to track “how many weight-reduction cases have been used,” so we add “number of cases used” to the DP state.

2. State Definition

We define the DP table as follows: - \(dp[j][w]\): The maximum value when selecting some subset of the jewels seen so far, using \(j\) weight-reduction cases, with a total weight of \(w\)

Here, the number of cases used \(j\) ranges over \(0 \leq j \leq K\), and the total weight \(w\) ranges over \(0 \leq w \leq C\).

3. Transition Logic

For each jewel \(i\) (original weight \(W_i\), value \(B_i\), halved weight \(W_{\text{half}} = \lfloor W_i / 2 \rfloor\)), we consider whether to select it or not. When selecting jewel \(i\), there are two options:

1. Select without using a weight-reduction case (only possible if \(W_i \leq C\))

   • The number of cases used \(j\) does not change.
   • \(dp[j][w] \leftarrow dp[j][w - W_i] + B_i\)

2. Select using a weight-reduction case (only possible if \(j \geq 1\) and \(W_{\text{half}} \leq C\))

   • The number of cases used increases from \(j-1\) to \(j\).
   • \(dp[j][w] \leftarrow dp[j-1][w - W_{\text{half}}] + B_i\)

Based on these transitions, by updating the DP table from the back (from larger values of \(w\) and \(j\)), we can prevent the duplication of selecting the same jewel multiple times, while saving memory by using a 2-dimensional array (over \(j\) and \(w\)).

4. Optimization Techniques (Constant Factor Optimization)

From the constraints, \(N(K+1)(C+1) \leq 2 \times 10^7\), and with a naive triple loop (jewels \(N\) \(\times\) cases \(K\) \(\times\) capacity \(C\)), there is a possibility of exceeding the time limit (TLE) in languages with relatively slow execution speed such as Python. Therefore, we apply the following optimizations:

• Limiting the reachable range: We keep track of max_w, the maximum total weight reachable from the jewels selected so far, and limit the upper bound of weight \(w\) explored in DP transitions to \(\min(C, \text{max\_w} + W_i)\). This significantly reduces the number of loop iterations in the early stages.
• Skipping impossible jewels: Jewels whose weight exceeds \(C\) even after halving (\(W_{\text{half}} > C\)) can never be carried, so they are ignored from the start.

---

Algorithm

1. Initialization:

   • Initialize all \(dp[j][w]\) to \(-1\) (unreachable). However, set \(dp[0][0] = 0\).
   • Prepare a variable max_w = 0 representing the maximum reachable weight so far.

2. DP Transitions: For each jewel \((W, B)\), perform the following:

   • Compute \(W_{\text{half}} = \lfloor W / 2 \rfloor\). If \(W_{\text{half}} > C\), skip this jewel.
   • Set the loop upper bound limit_w appropriately depending on whether a case is used or not.
   • Loop over the number of cases used \(j\) from \(K\) down to \(0\) in reverse order.
     • When \(j > 0\), update \(dp[j][w]\) considering both the transition using a case (transition from \(dp[j-1]\)) and the transition without using a case (transition from \(dp[j]\)).
     • When \(j = 0\), update \(dp[0][w]\) considering only the transition without using a case.
   • Update max_w.

3. Output the Answer:

   • The answer is the maximum value across the entire DP table (the maximum of \(dp[j][w]\) over all \(j, w\)).

---

Complexity

Time Complexity: \(O(NKC)\)

Even in the worst case, the number of loop iterations is proportional to \(N \times (K+1) \times (C+1)\). Since the constraints guarantee \(N(K+1)(C+1) \leq 2 \times 10^7\), an implementation with constant factor optimizations can comfortably fit within the time limit.

Space Complexity: \(O(KC)\)

The memory required for the DP table is of size \((K+1) \times (C+1)\). Since \(K \le 30\) and \(C \le 10^5\), the maximum number of elements is approximately \(3.1 \times 10^6\), which is very safe with respect to the memory limit.

---

Implementation Notes

• Reverse-order loops: To prevent the problem from becoming an “unbounded knapsack problem” where the same jewel can be selected more than once, the loops over weight \(w\) and number of cases \(j\) must always iterate from larger values (in reverse order).

• Conditional branching in transitions: If the original weight \(W\) of a jewel exceeds \(C\), the jewel cannot be selected without using a case. In the code, we branch on whether W <= C to prevent invalid transitions (out-of-bounds array access or inappropriate state updates).

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    C = int(data[1])
    K = int(data[2])
    
    items = []
    idx = 3
    for _ in range(N):
        B = int(data[idx])
        W = int(data[idx+1])
        items.append((W, B))
        idx += 2
        
    dp = [[-1] * (C + 1) for _ in range(K + 1)]
    dp[0][0] = 0
    
    max_w = 0
    for W, B in items:
        W_half = W // 2
        if W_half > C:
            continue
        
        if W <= C:
            limit_w = min(C, max_w + W)
        else:
            limit_w = min(C, max_w + W_half)
            
        for j in range(K, -1, -1):
            dp_j = dp[j]
            if j > 0:
                dp_j_prev = dp[j-1]
                if W <= C:
                    for w in range(limit_w, W - 1, -1):
                        v1 = dp_j[w - W]
                        v2 = dp_j_prev[w - W_half]
                        mx = dp_j[w]
                        if v1 != -1:
                            t = v1 + B
                            if t > mx: mx = t
                        if v2 != -1:
                            t = v2 + B
                            if t > mx: mx = t
                        dp_j[w] = mx
                    
                    start_w = min(limit_w, W - 1)
                    for w in range(start_w, W_half - 1, -1):
                        v2 = dp_j_prev[w - W_half]
                        mx = dp_j[w]
                        if v2 != -1:
                            t = v2 + B
                            if t > mx: mx = t
                        dp_j[w] = mx
                else:
                    for w in range(limit_w, W_half - 1, -1):
                        v2 = dp_j_prev[w - W_half]
                        mx = dp_j[w]
                        if v2 != -1:
                            t = v2 + B
                            if t > mx: mx = t
                        dp_j[w] = mx
            else:
                if W <= C:
                    for w in range(limit_w, W - 1, -1):
                        v1 = dp_j[w - W]
                        mx = dp_j[w]
                        if v1 != -1:
                            t = v1 + B
                            if t > mx: mx = t
                        dp_j[w] = mx
                        
        if W <= C:
            max_w = min(C, max_w + W)
        else:
            max_w = min(C, max_w + W_half)
            
    ans = 0
    for j in range(K + 1):
        for w in range(C + 1):
            if dp[j][w] > ans:
                ans = dp[j][w]
    print(ans)

if __name__ == '__main__':
    solve()

---

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