Overview

This problem asks us to maximize the total value (completion points) by selecting from multiple candidates (homework assignments) within a limited time constraint \(M\). This is a classic “0/1 Knapsack Problem”.

Analysis

1. Is Brute Force Feasible?

Since each homework assignment has two choices — “do it” or “don’t do it” — examining all combinations results in \(2^N\) possible patterns. Given the constraint \(N=100\), the number of combinations is \(2^{100} \approx 1.26 \times 10^{30}\), which is far too large to compute within the time limit.

2. Is a Greedy Approach Feasible?

A greedy approach of “selecting assignments in order of highest points per minute” might come to mind, but this method does not guarantee an optimal solution. For example, consider the case where the remaining time is 10 minutes, and there is one assignment worth “10 points, 10 minutes” and two assignments each worth “6 points, 5 minutes”. - In terms of efficiency, the former has \(10/10 = 1\), and the latter has \(6/5 = 1.2\). - If we greedily pick the more efficient latter first, we can only select “6 points × 1 assignment,” and with only 5 minutes remaining, we cannot select the former. - However, selecting two of the latter assignments yields \(6+6=12\) points, which gives a higher score.

As this shows, under the condition that items cannot be split (it’s either 0 or 1), a simple efficiency-based ordering does not work, so we use Dynamic Programming (DP).

Algorithm

Solving with Dynamic Programming (DP)

We compute while recording “the maximum points obtainable using the first \(i\) homework assignments with a total time of \(j\) minutes.”

To save memory, we solve this using a 1-dimensional array DP. - Array definition: dp[j] = the maximum completion points obtainable with a total time of at most \(j\) minutes - Initial state: dp[0...M] = 0

Recurrence Relation

When considering a new homework assignment (points \(R_i\), time \(T_i\)), we update for each time \(j\) as follows: $\(dp[j] = \max(dp[j], dp[j - T_i] + R_i)\)\( This means we compare "not doing the current assignment (the previous maximum)" with "doing the current assignment (the maximum at remaining time \)j - T_i$ plus the current points)” and adopt the larger value.

Complexity

• Time Complexity: \(O(N \times M)\)
  • This is because we iterate over time \(M\) within a loop over the \(N\) homework assignments.
  • Under the given constraints, this is \(100 \times 10^5 = 10^7\), which is well within the time limit even in Python.
• Space Complexity: \(O(M)\)
  • This is because we maintain a 1-dimensional array corresponding to \(M\) minutes.

Implementation Notes

• Reverse-order Loop: When updating the DP with a 1-dimensional array, the inner loop (over time) must iterate in reverse order from \(M\) down to \(T_i\). If updated in forward order, there is a risk of using the “value after using the same assignment once” to add the same assignment again (duplicate usage).

• Handling Large Values: The completion points \(R_i\) can be up to \(10^9\), and the total can become very large. Since Python natively supports arbitrary-precision integers, we can compute directly without worrying about overflow.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 宿題の数 N と残り時間 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # dp[j] は、合計時間が j 分以下であるときに得られる完成度ポイントの最大値を表します
    # 初期値はすべて0（どの宿題も選んでいない状態）
    dp = [0] * (M + 1)
    
    # 各宿題について情報を取得し、DPテーブルを更新します
    for i in range(N):
        # 宿題 i の完成度ポイント r と必要時間 t
        r = int(input_data[2 + 2*i])
        t = int(input_data[3 + 2*i])
        
        # 0/1ナップサック問題の標準的な更新方法です
        # 各宿題を1回だけ選べるようにするため、後ろから（Mからtまで）更新します
        for j in range(M, t - 1, -1):
            # 宿題 i を選んだ場合のポイント
            new_val = dp[j - t] + r
            # 既存のポイントより大きければ更新
            if new_val > dp[j]:
                dp[j] = new_val
                
    # dp[M] には残り時間 M 分以内での最大完成度ポイントが格納されています
    print(dp[M])

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.