Overview

Given a remaining time of \(M\) minutes, select some homework assignments (each at most once) to maximize the total completeness points. This is solved using dynamic programming as a classic 0/1 knapsack problem.

Analysis

• Each homework assignment has two choices: “do it / don’t do it,” and the same homework cannot be done multiple times. Therefore, “maximize the value (completeness) without exceeding time \(M\)” = 0/1 knapsack formulation.
• A naive exhaustive search has \(2^N\) possible selections of homework. Since \(N \le 100\), \(2^{100}\) is far too large to compute and would result in TLE.
• Also, greedy approaches such as “sort by highest completeness” or “sort by highest completeness/time ratio” are not generally correct.
  Example: \(M=10\), (R,T) = (10,6), (9,5), (9,5)
  Greedily choosing (10,6) leaves 4 minutes remaining, so no other assignment can be selected, giving a total of 10 points.
  However, (9,5)+(9,5)=18 points is optimal.
• Therefore, we use DP that tracks “how much time has been used” as the state and updates the optimal value while processing homework assignments in order.

Algorithm

DP Array Definition
- \(dp[w]\) := “the maximum completeness points obtainable when using exactly \(w\) minutes of total time” - Unreachable states are initialized with a very small value (\(-\infty\)). - The initial state is “do nothing, use 0 time,” so \(dp[0]=0\) and all others are \(-\infty\).

Transition (processing homework \((R_i, T_i)\)) - If we select this homework, we must have previously achieved time \((w-T_i)\), and we add \(T_i\) minutes and \(R_i\) points: $\( dp[w] = \max(dp[w],\ dp[w-T_i] + R_i) \)\( - However, to ensure the same homework is not used multiple times (0/1 property), \)w\( must be iterated **from large to small** (\)M \to T_i\(). If we update from small to large, the already-updated \)dp$ values would be reused for the same homework, resulting in an “unlimited selections” situation (a different problem).

Answer - The condition is “total time at most \(M\),” so it doesn’t have to be exactly \(M\). Therefore, we output: $\( \max_{0 \le w \le M} dp[w] \)$ (in the code, this is max(dp)).

Complexity

• Time complexity: \(O(NM)\)
  (for each homework, we update \(w=0..M\) once)
• Space complexity: \(O(M)\)
  (only a 1-dimensional DP array)

Implementation Notes

• To represent unreachable states, use a sufficiently small value like NEG = -10**30, and only perform transitions when dp[w-t] != NEG (to prevent invalid additions).

• The update order must be descending (for w in range(M, t-1, -1):). This is the key point of the 0/1 knapsack.

• Completeness \(R_i\) can be up to \(10^9\), and the total can be even larger, so Python’s int (arbitrary precision) handles this safely.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M = map(int, input().split())
    NEG = -10**30
    dp = [NEG] * (M + 1)
    dp[0] = 0

    for _ in range(N):
        r, t = map(int, input().split())
        for w in range(M, t - 1, -1):
            prev = dp[w - t]
            if prev != NEG:
                val = prev + r
                if val > dp[w]:
                    dp[w] = val

    print(max(dp))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.