abc 145 E: All-you-can-eat (python)

自力AC。解説とは若干違った。むしろ解説がよく分からん。
ぱっと見で01ナップザック問題じゃんとなり、dpするだけなのかと普通の (N*T) の二次元dp を実装したらサンプル３が合わず考えると、T-1 秒までなら T 秒を超えても注文ができるのが原因だと分かる。なのでこれを自然にケアする方法を考えて
注文は T 秒未満、食べきるのは T + max(A) 秒未満になるような a,b の選び方を実装しようと思った。なので dp[i][j] = i 個目まで見たときに j 秒経過しているときの満足度の最大値
として実装した。
しかしこの実装だと

3 60
30 10
30 20
20 30

みたいなケースで T < 60 でないと満足度を加算しないため、
dp[3][80] = dp[2][60] + 30 としてくれないため答えが合わない。
そこで a の昇順でソートすることで解決した。
計算量の仕方はよく分からないが最悪 O(N*(T+max(A))) ぐらいじゃないかな
pypy でないと通らなかった。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n,t = map(int,readline().split())
f = []
m = 0
for i in range(n):
  p,q = map(int,readline().split())
  m = max(m,p)
  f.append((p,q))
  
f.sort() # sort
dp = [[0]*(t+m) for i in range(n+1)]

for i,c in enumerate(f):
  a,b = c
  for j in range(t+m):
    if j-a >= t: # 注文できるのは T 秒未満のときだけ
      break
    if j < a : # この辺は普通の01ナップザックと同じ
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-a]+b)
      
print(max(dp[n]))