Overview

This problem is an application of the knapsack problem, where you select a subset of homework assignments within a time limit of \(M\) minutes to maximize the total completeness points earned.

Analysis

This problem is known as the classic “0-1 Knapsack Problem.” Each homework assignment has a “weight (required time \(T_i\))” and a “value (completeness points \(R_i\)),” and the goal is to maximize the total value within the time limit \(M\).

A naive brute-force approach (considering all subsets) would require \(2^{100}\) combinations since the number of homework assignments \(N\) is at most 100, which is far too large to compute (TLE). Additionally, a greedy approach (e.g., selecting in order of highest “points/time” ratio) does not guarantee an optimal solution for this problem, resulting in WA.

Therefore, using dynamic programming (DP) is effective. We define the DP table dp[t] as “the maximum completeness points obtainable within time \(t\).” By updating from larger time values to smaller ones for each homework assignment, we prevent selecting the same homework multiple times.

Algorithm

We use dynamic programming (DP).

DP Definition

• dp[t]: The maximum completeness points obtainable within time \(t\)

Update Method

For each homework assignment \(i\) (completeness \(r = R_i\), required time \(t = T_i\)): - Iterate time \(j\) from \(M\) down to \(t\) in reverse order, and update as follows:

  if dp[j] < dp[j - t] + r:
      dp[j] = dp[j - t] + r

• By iterating in reverse order, we prevent selecting the same homework multiple times (each is used at most once)

Final Answer

• max(dp) is the desired maximum value

Complexity

• Time complexity: \(O(N \times M)\)
• Space complexity: \(O(M)\)

Implementation Notes

• The DP table update must always be done in reverse order. This avoids the bug of selecting the same item (homework) multiple times.

• Initialize with dp[0] = 0, and all other dp[t] values are initialized to 0.

• By outputting max(dp) at the end, we obtain the maximum points achievable within time \(M\).

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    R = []
    T = []
    
    for i in range(N):
        R.append(int(data[2 + 2 * i]))
        T.append(int(data[3 + 2 * i]))
    
    # DPテーブル: dp[t] = 時間t以内で得られる最大の完成度ポイント
    dp = [0] * (M + 1)
    
    for i in range(N):
        r = R[i]
        t = T[i]
        # 逆順に更新しないと、同じアイテムを複数回使ってしまう可能性がある
        for j in range(M, t - 1, -1):
            if dp[j] < dp[j - t] + r:
                dp[j] = dp[j - t] + r
    
    print(max(dp))

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.