Overview

Given \(N\) pieces of equipment, select one or more such that the total defense is at least \(K\), and maximize the total attack power. This can be solved as a variant of the 0-1 knapsack problem with constraints.

Analysis

Naive Approach (Exhaustive Search)

Since each of the \(N\) pieces of equipment has 2 choices (“select” or “don’t select”), an exhaustive search would require examining \(2^N\) combinations. When \(N \leq 100\), \(2^{100}\) is an astronomically large number, making this approach completely infeasible.

Key Insight

This problem is a variant of the 0-1 knapsack problem. The standard knapsack problem has the constraint “total weight is at most \(K\)”, but in this problem the constraint is “total defense is at least \(K\)”.

The key observation here is that there is no need to distinguish defense values that exceed \(K\). Whether the total defense is \(K\) or \(K+100\), the condition “at least \(K\)” is equally satisfied. Therefore, we can restrict the defense values in our DP states to the range \(0\) through \(K\), merging all values \(K\) or above into a single state \(K\).

Algorithm

We use a 0-1 knapsack DP.

• State: \(dp[w]\) = the maximum total attack power achievable by selecting equipment whose total defense is exactly \(w\) (where \(w = K\) represents “defense of \(K\) or more”)
• Initial state: \(dp[0] = 0\), all others are \(-1\) (unreachable)
• Transition: For each piece of equipment \((W_i, S_i)\), for every \(w\) where \(dp[w]\) is valid, consider the transition to a new defense value \(\min(w + W_i, K)\): $\(dp'[\min(w + W_i, K)] = \max(dp'[\min(w + W_i, K)],\ dp[w] + S_i)\)$

By using \(\min(w + W_i, K)\), all defense values of \(K\) or more are consolidated into index \(K\).

• Since each piece of equipment can be used at most once, we update using a copy of the original \(dp\) array (new_dp = dp[:]) during transitions.

Finally, if \(dp[K]\) is not \(-1\), it is the answer; if it is \(-1\), then no valid selection exists.

Concrete Example

For \(N=3, K=5\) with equipment \((W, S) = (3, 10), (2, 8), (4, 15)\): - Selecting equipment 1 and 2: defense \(3+2=5 \geq 5\), attack \(10+8=18\) - Selecting equipment 1 and 3: defense \(3+4=7 \geq 5\), attack \(10+15=25\) - Selecting equipment 2 and 3: defense \(2+4=6 \geq 5\), attack \(8+15=23\)

Therefore the answer is \(25\).

Complexity

• Time complexity: \(O(N \times K)\)
  • For each of the \(N\) pieces of equipment, we scan states from \(0\) to \(K\)
• Space complexity: \(O(K)\)
  • The size of the DP table

Since \(N \leq 100\) and \(K \leq 10^4\), the maximum number of operations is approximately \(100 \times 10^4 = 10^6\), which is sufficiently fast.

Implementation Notes

• Clamping defense to the upper bound: By using nw = min(w + W, K), all defense values of \(K\) or more are consolidated into index \(K\). This is the most important point of this problem.

• 0-1 knapsack update method: To ensure each piece of equipment is used at most once, we create a copy with new_dp = dp[:] before updating. In a standard 0-1 knapsack, this is typically handled by iterating in reverse order, but in this problem, since the transition destination min(w+W, K) can cause multiple values of \(w\) to map to the same index, using a copy is safer.

• Managing unreachable states: We treat \(-1\) as “unreached” and skip transitions from states where the source is \(-1\).

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    
    items = []
    for i in range(N):
        W = int(input_data[idx]); idx += 1
        S = int(input_data[idx]); idx += 1
        items.append((W, S))
    
    # dp[w] = maximum attack power achievable with exactly defense w
    # We cap w at K since any defense >= K is equivalent for our purposes
    # dp[w] for w = 0..K, where dp[K] represents "defense >= K"
    
    NEG_INF = -1
    dp = [NEG_INF] * (K + 1)
    dp[0] = 0
    
    for W, S in items:
        # Traverse in reverse to ensure each item is used at most once
        new_dp = dp[:]
        for w in range(K + 1):
            if dp[w] == NEG_INF:
                continue
            nw = min(w + W, K)
            if new_dp[nw] < dp[w] + S:
                new_dp[nw] = dp[w] + S
        dp = new_dp
    
    if dp[K] == NEG_INF:
        print(-1)
    else:
        print(dp[K])

solve()

---

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