Overview

This is a problem where you select equipment such that the total defense is at least \(K\), and you want to maximize the total attack power.

Analysis

Each piece of equipment has two choices: “select / don’t select.” Checking all combinations would result in \(2^N\) possibilities, and when \(N\) is up to 100, the computation becomes enormous. Therefore, we consider solving this efficiently using dynamic programming (DP).

We construct a DP table that uses the total defense as a state and maintains the maximum attack power for that state. Since the maximum total defense is at most around \(10^6\) (\(N \leq 100\), \(W_i \leq 10^4\)), the size of the DP table is within a manageable range.

Algorithm

1. Initialization: Prepare an array dp that stores the maximum attack power when the total defense is \(j\). The initial value is dp[0] = 0 (the state where nothing is selected), and all other entries are initialized to -1 to indicate that the state has not been reached.
2. Updating the DP table: For each piece of equipment, update from the current total defense \(j\) to the new state \(j + w_i\) by adding that equipment. Update only when the total attack power becomes larger (similar to the knapsack problem).
3. Extracting the answer: Among all states where the total defense is at least \(K\), find the maximum attack power. If no such state exists, output -1.

Complexity

• Time complexity: \(O(N \cdot \sum W_i)\)
• Space complexity: \(O(\sum W_i)\)

Implementation Notes

• When processing equipment one by one, update the DP table from back to front to prevent selecting the same piece of equipment more than once.

• The maximum possible total defense is the sum of all equipment’s defense values, so compute this in advance.

• If the required defense \(K\) is greater than the total defense of all equipment, output -1 immediately and terminate.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    K = int(data[1])
    W = []
    S = []
    index = 2
    for i in range(n):
        w = int(data[index])
        s = int(data[index+1])
        index += 2
        W.append(w)
        S.append(s)
    
    max_w = max(W) if n > 0 else 0
    max_total_w = sum(W)
    if K > max_total_w:
        print(-1)
        return
        
    dp = [-1] * (max_total_w + 1)
    dp[0] = 0
    for i in range(n):
        w = W[i]
        s = S[i]
        for j in range(max_total_w, w - 1, -1):
            if dp[j - w] != -1:
                if dp[j] < dp[j - w] + s:
                    dp[j] = dp[j - w] + s
                    
    ans = -1
    for j in range(K, max_total_w + 1):
        if dp[j] > ans:
            ans = dp[j]
            
    print(ans if ans != -1 else -1)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.