Problem p02863 (python)

Fixed submission:
n, t = map(int, input().split())
 
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
 
a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
 
dp = [[0 for j in range(t+1)] for i in range(n+1)]
 
for i in range(n):
    for j in range(t):
        if j + a[i] <= t-1:
            if dp[i+1][j + a[i]] < dp[i][j] + b[i]:
                dp[i+1][j + a[i]] = dp[i][j] + b[i]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
 
ans = 0
 
for i in range(n):
    ans = max(ans, dp[i][t-1] + b[i])
 
print(ans)

Buggy submission (verdict: Runtime Error):
n,t = map(int,input().split())
s = []
dp = [[0]*(t) for _ in range(n+1)]
for _ in range(n):
    a,b = map(int,input().split())
    s.append([a,b])
s.sort()
ans = 0
#dp[i+1][j] .. i番目までのものから時間の総和がt以下となる時
for i in range(n):
    ans = max(ans,max(dp[:i][:])+reward) #それを最後に食した場合答えとなる
    time = s[i][0]
    reward = s[i][1]
    for j in range(t):
        if time > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-time])
print(ans)

Buggy submission (verdict: Runtime Error):
n, t = map(int, input().split())
 
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
 
a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
 
dp = [[0 for _ in range(t)] for _ in range(n+1)]
 
for i in range(n):
    for j in range(t):
        if j + a[i] <= t-1:
            if dp[i+1][j + a[i]] < dp[i][j] + b[i]:
                dp[i+1][j + a[i]] = dp[i][j] + b[i]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
 
ans = 0
for i in range(N):
    ans = max(ans,dp[i][t-1]+b[i])
    
print(ans)

Buggy submission (verdict: Runtime Error):
#ABC145 E
N,T = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
ab.sort()

a = []
b = []
for ai, bi in ab:
    a.append(ai)
    b.append(bi)
    
dp = [[0 for j in range(T)] for _ in range(N+1)]
# i番目より前まで注文してT分以内(max T-1)で完食する
    
for i in range(N):
    for t in range(T): 
        if j + a[i] <= t-1:
            if dp[i+1][j + a[i]] < dp[i][j] + b[i]:
                dp[i+1][j + a[i]] = dp[i][j] + b[i]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]

#一番遅いものをラスト(T-1分)に注文
#i番目をラストに注文 = dp[i][t-1] + b[i]
ans = 0
for i in range(N):
    ans = max(ans,dp[i][t-1]+b[i])
    
print(ans)

Buggy submission (verdict: Runtime Error):
#ABC145 E
N,T = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N)]
ab.sort()

for ai, bi in ab:
    a.append(ai)
    b.append(bi)
    
dp = [[0]*T for _ in range(N+1)]
# i番目より前まで注文してT分以内(max T-1)で完食する
def chmax(a,b):
    if a < b:
        return b
    else:
        return a 
    
for i in range(N):
    for t in range(T): #T-1分がmax
        if t+a[i] <= T-1:
        	dp[i+1][t+a[i]] =chmax(dp[i+1][t+a[i]],dp[i][t]+b[i])
        
        dp[i+1][t] = chmax(dp[i+1][t],dp[i][t])

#一番遅いものをラスト(T-1分)に注文
#i番目をラストに注文 = dp[i][t-1] + b[i]
ans = 0
for i in range(N):
    ans = chmax(ans,dp[i][t-1]+b[i])
    
print(ans)

Buggy submission (verdict: Runtime Error):
n,t = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
sorted(ab)
dp = [[-1 for i in range(t)] for j in range(n+1)]

def dfs(i,j):
    if dp[i][j] >= 0:
        return dp[i][j]
      
    if i == n:
        res = 0
    elif j == 0:
        res = 0
    elif ab[i][0] >= j:
        res = max(ab[i][1],dfs(i+1,j))
    elif ab[i][0] < j:
        res = max(dfs(i+1,j),dfs(i+1,j-ab[i][0])+ab[i][1])
    dp[i][j] = res
    return res

print(dfs(0,t-1))