Overview

This is a knapsack problem where, for each gem, we consider 3 options: “don’t select it,” “select it as-is,” or “select it using a weight-reduction case.”

We find the maximum total value using dynamic programming that also tracks the number of weight-reduction cases used.

Analysis

In a standard 0/1 knapsack, for each item we consider “select / don’t select.”

In this problem, when selecting gem \(i\), there are two further options:

• Select as-is
  
  • Weight \(W_i\)
  • No case used
• Select with weight reduction
  
  • Weight \(\left\lfloor \frac{W_i}{2} \right\rfloor\)
  • Uses 1 case

However, multiple cases cannot be used on the same gem, and each gem can be selected at most once.

For example, if we simply treat “normal version of a gem” and “weight-reduced version of a gem” as separate items in the knapsack, we could end up selecting both versions of the same gem, which would be incorrect.

Therefore, we process each gem one by one, maintaining a DP with the following states:

• How many cases have been used so far
• What is the current remaining weight capacity

Algorithm

Define \(dp[j][c]\) as follows:

The maximum value achievable from the gems processed so far, using at most \(j\) weight-reduction cases, with total weight at most \(c\)

The key point here is “at most \(j\)” rather than “exactly \(j\),” since it’s fine to have leftover cases.

Let the gem’s value be \(b\), its weight be \(w\), and its weight after reduction be

\[ h = \left\lfloor \frac{w}{2} \right\rfloor \]

For this gem, there are 3 possible transitions:

1. Don’t select

Do nothing.

\[ dp[j][c] \]

remains unchanged.

2. Select as-is

No case is used, and weight \(w\) is consumed.

\[ dp[j][c] = \max(dp[j][c], dp[j][c-w] + b) \]

This is only possible when \(c \geq w\).

3. Select with weight reduction

One case is used, and weight \(h\) is consumed.

\[ dp[j][c] = \max(dp[j][c], dp[j-1][c-h] + b) \]

This is only possible when \(j \geq 1\) and \(c \geq h\).

For example, a gem with weight \(w=7\) has reduced weight \(h=3\).

• When capacity \(c=5\)
  
  • Normal weight \(7\) doesn’t fit
  • With weight reduction, weight \(3\) fits
• When capacity \(c=8\)
  
  • Fits even without reduction
  • Also fits with reduction

As shown, the available choices change depending on the capacity.

When updating the DP, to ensure each gem is used at most once, we loop in the following order:

• Case count \(j\) from large to small
• Weight \(c\) from large to small

This prevents using the same gem multiple times.

The final answer, given capacity \(C\) and at most \(K\) cases available, is:

\[ dp[K][C] \]

In the code, active is used to manage the number of DP rows currently in use, to avoid creating rows for case counts that haven’t been reached yet.

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

• dp[j][c] is maintained as “using at most \(j\) cases.”

• The weight after reduction is computed as h = w >> 1. This is equivalent to \(\left\lfloor \frac{w}{2} \right\rfloor\).

• Updating \(j\) and \(c\) in descending order prevents selecting the same gem multiple times.

• Gems with \(W_i > C\) can never fit as-is, so only the weight-reduction transition is performed for them.

• Since the value \(B_i\) can be up to \(10^9\) and the total can become large, long long is needed in C++. In Python, the standard int handles this without issues.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, C, K = data[0], data[1], data[2]

    dp = [None] * (K + 1)
    dp[0] = [0] * (C + 1)

    active = 0
    idx = 3

    for _ in range(N):
        b = data[idx]
        w = data[idx + 1]
        idx += 2
        h = w >> 1

        if active < K:
            na = active + 1
            dp[na] = dp[active].copy()
        else:
            na = active

        if w <= C:
            ww = w
            hh = h

            for j in range(na, 0, -1):
                row = dp[j]
                prev = dp[j - 1]

                for c in range(C, ww - 1, -1):
                    x = row[c - ww]
                    y = prev[c - hh]
                    if y > x:
                        x = y
                    x += b
                    if x > row[c]:
                        row[c] = x

                for c in range(ww - 1, hh - 1, -1):
                    x = prev[c - hh] + b
                    if x > row[c]:
                        row[c] = x

            row = dp[0]
            for c in range(C, ww - 1, -1):
                x = row[c - ww] + b
                if x > row[c]:
                    row[c] = x
        else:
            hh = h
            for j in range(na, 0, -1):
                row = dp[j]
                prev = dp[j - 1]
                for c in range(C, hh - 1, -1):
                    x = prev[c - hh] + b
                    if x > row[c]:
                        row[c] = x

        active = na

    print(dp[active][C])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.