Overview

This is a “0-1 Knapsack Problem” where you select some homework assignments to maximize the total completion points within a time limit of \(M\) minutes.

Analysis

The Essence of the Problem

This problem involves repeatedly making binary choices of “select” or “don’t select” for each homework assignment to maximize points obtained within the time limit. This is a famous problem known as the 0-1 Knapsack Problem.

Naive Approach and Its Issues

The simplest method is to try all patterns of “do/don’t do” for each of the \(N\) homework assignments. However, this requires examining \(2^N\) combinations, and when \(N = 100\), \(2^{100}\) becomes an astronomically large number, resulting in TLE (Time Limit Exceeded).

Solution: Dynamic Programming (DP)

To avoid redundant calculations, we use dynamic programming.

We process homework assignments one by one while recording “the maximum points obtainable when using time \(j\)”.

Algorithm

DP Definition

\(dp[j]\) = the maximum completion points when using at most \(j\) minutes

Transition Logic

For each homework assignment \((R_i, T_i)\), consider the case of using time \(j\): - If we don’t select this homework: \(dp[j]\) remains unchanged - If we select this homework: \(dp[j-T_i] + R_i\) (add points \(R_i\) to the state from \(T_i\) minutes ago)

The larger of these two values becomes the new \(dp[j]\).

Concrete Example

For \(N=3, M=5\) with homework \((R_1, T_1) = (4, 2), (R_2, T_2) = (5, 3), (R_3, T_3) = (3, 2)\):

1. Initial state: \(dp = [0, 0, 0, 0, 0, 0]\) (time 0 to 5)
2. After processing homework 1 \((4, 2)\): \(dp = [0, 0, 4, 4, 4, 4]\)
3. After processing homework 2 \((5, 3)\): \(dp = [0, 0, 4, 5, 5, 9]\)
4. After processing homework 3 \((3, 2)\): \(dp = [0, 0, 4, 5, 7, 9]\)

The answer is \(\max(dp) = 9\) (selecting homework 1 and homework 2)

Why Update in Reverse Order?

If we update in the forward direction (from \(j = 0\) to \(M\)), we might use the same homework multiple times.

For example, when processing homework \((R=4, T=2)\): - \(dp[2] = dp[0] + 4 = 4\) (used once) - \(dp[4] = dp[2] + 4 = 8\) (used twice!)

By updating in reverse order (from \(j = M\) to \(T\)), we reference old \(dp\) values that haven’t been updated yet, guaranteeing that each homework is used at most once.

Complexity

• Time Complexity: \(O(N \times M)\)
  • For each of the \(N\) homework assignments, we perform \(M\) loop iterations
  • With \(N = 100, M = 10^5\), this is at most around \(10^7\) operations
• Space Complexity: \(O(M)\)
  • The size of the 1-dimensional array \(dp\)

Implementation Notes

• Saving space with 1D DP: While you could use a 2D array \(dp[i][j]\) (using time \(j\) with the first \(i\) homework assignments), using a 1D array with reverse-order updates reduces memory usage
• Loop range: range(M, T - 1, -1) iterates in reverse from \(j = M\) to \(j = T\) (when \(j < T\), we cannot select the homework, so we skip)
• Final answer: max(dp) gives the maximum points achievable within time \(M\) (this will be the same value as dp[M])

Source Code

def solve():
    N, M = map(int, input().split())
    items = []
    for _ in range(N):
        R, T = map(int, input().split())
        items.append((R, T))
    
    # 0-1 Knapsack Problem
    # dp[j] = maximum completion points when using time j
    dp = [0] * (M + 1)
    
    for R, T in items:
        # Update in reverse order to ensure each item is used at most once
        for j in range(M, T - 1, -1):
            dp[j] = max(dp[j], dp[j - T] + R)
    
    print(max(dp))

solve()

---

This editorial was generated by claude4.5opus.