Overview

This problem extends the weight-limited 0/1 knapsack problem with an additional condition: “you can halve the weight of gems using up to \(K\) lightweight cases.” It is solved using DP with the number of cases used as an additional dimension.

Analysis

Key Observation

This problem is an extension of the standard 0/1 knapsack problem. For each gem, there are three choices:

1. Do not take it
2. Take it as-is (weight \(W_i\))
3. Take it using a lightweight case (weight \(\lfloor W_i / 2 \rfloor\), consuming 1 case)

Problem with the Naive Approach

Simply brute-forcing “which gems to use cases on” results in \(\binom{N}{K}\) combinations, which explodes when \(N\) is large.

Solution Strategy

We incorporate the number of cases used into the DP state. By defining \(dp[k][c]\) as “the maximum value obtainable using at most \(k\) lightweight cases with total weight at most \(c\),” we can solve this in the standard knapsack fashion, processing each gem one at a time.

Algorithm

DP Definition

\[dp[k][c] = \text{maximum value obtainable using at most } k \text{ cases within capacity } c\]

Transitions

For each gem \((B_i, W_i)\) (with halved weight \(hw_i = \lfloor W_i/2 \rfloor\)), iterate \(k\) from \(K\) down to \(0\) and \(c\) from \(C\) downward:

• Take as-is (when \(c \geq W_i\)): $\(dp[k][c] \leftarrow \max(dp[k][c],\ dp[k][c - W_i] + B_i)\)$

• Take using a case (when \(k > 0\) and \(c \geq hw_i\)): $\(dp[k][c] \leftarrow \max(dp[k][c],\ dp[k-1][c - hw_i] + B_i)\)$

By processing \(k\) and \(c\) in descending order, we prevent selecting the same gem multiple times (a standard technique for 0/1 knapsack).

Concrete Example

Example: \(N=2, C=10, K=1\), Gem 1: \((B=100, W=8)\), Gem 2: \((B=80, W=6)\)

• Using a case on Gem 1 reduces its weight to 4 → Gem 1 (weight 4) + Gem 2 (weight 6) = total weight 10 with value 180
• Without a case, weight 8+6=14 > 10, so both cannot be taken

The DP automatically finds the optimal assignment.

Complexity

• Time complexity: \(O(N \cdot (K+1) \cdot C)\)
  • The constraint \(N(K+1)(C+1) \leq 2 \times 10^7\) ensures it fits within the time limit
• Space complexity: \(O((K+1) \cdot C)\)

Implementation Details

1. Descending loops: Since this is a 0/1 knapsack, both capacity \(c\) and case count \(k\) are updated from larger values downward. This prevents duplicate selection of the same item.

2. Speedup via case splitting: When \(W_i > C\), the gem can never fit without a case, so only the case-usage transition is performed. Additionally, even when \(W_i \leq C\), in the range \(hw_i \leq c < W_i\), only the case-usage transition is valid, so the loop is split to reduce unnecessary comparisons.

3. Bit shift: \(\lfloor W_i / 2 \rfloor\) is computed as w >> 1 for a slight speedup.

4. Speed optimization in Python: Input is read all at once using sys.stdin.buffer.read(), and DP table rows are bound to local variables (dpk, dpk1) to reduce attribute access overhead.

   Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    C = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    items = []
    for i in range(N):
        b = int(data[idx]); idx += 1
        w = int(data[idx]); idx += 1
        items.append((b, w))
    
    # dp[k][c] = max value using at most k cases, weight at most c
    dp = [[0] * (C + 1) for _ in range(K + 1)]
    
    for b, w in items:
        hw = w >> 1
        for k in range(K, -1, -1):
            dpk = dp[k]
            if k > 0:
                dpk1 = dp[k - 1]
                if w <= C:
                    for c in range(C, w - 1, -1):
                        val = dpk[c]
                        nv = dpk[c - w] + b
                        if nv > val:
                            val = nv
                        nv = dpk1[c - hw] + b
                        if nv > val:
                            val = nv
                        dpk[c] = val
                    upper = min(w - 1, C)
                    for c in range(upper, hw - 1, -1):
                        nv = dpk1[c - hw] + b
                        if nv > dpk[c]:
                            dpk[c] = nv
                else:
                    if hw <= C:
                        for c in range(C, hw - 1, -1):
                            nv = dpk1[c - hw] + b
                            if nv > dpk[c]:
                                dpk[c] = nv
            else:
                if w <= C:
                    for c in range(C, w - 1, -1):
                        nv = dpk[c - w] + b
                        if nv > dpk[c]:
                            dpk[c] = nv
    
    print(dp[K][C])

main()

---

This editorial was generated by claude4.6opus-thinking.