Problem p02863 (python)

Fixed submission:

N, T = map(int, input().split())

AB = [tuple(map(int, input().split())) for _ in range(N)]


AB.sort()

dp = [[0 for _ in range(T)] for _ in range(N+1)]




for i in range(N):
    for j in range(T):
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1] )


ans = 0
for i, d in enumerate(dp):
    # dp[i][:]にはi-1番目までで最大の満足度が入れられてるから、ABのi以降（使ってないから）で一番大きいのを足す
    mb = 0
    for a,b in AB[i:]:
        mb = max(mb, b)
    ans = max(ans, d[-1] + mb)

print(ans)

Buggy submission (verdict: Runtime Error):

N, T = map(int, input().split())

AB = [tuple(map(int, input().split())) for _ in range(N)]


AB.sort()

dp = [[0 for _ in range(T)] for _ in range(N+1)]




for i in range(N):
    for j in range(T):
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1] )


# 使ってないものを探す

used = [False] * N
j = T-1
#print("j =", j)
for i in reversed(range(N)):
    if dp[i+1][j] == 0:
        break
    #for j in reversed(range(T)):
    # i を使う場合
    #print(i, dp[i][j - AB[i][0]] + AB[i][1] , dp[i][j])
    #print("i, j, dp(i+1,j), dp[i+1][j - AB[i][0]] + AB[i][1] ", i, j, dp[i+1][j], dp[i+1][j - AB[i][0]] + AB[i][1] )
    #print(i,j, AB[i][0])
    if dp[i][j - AB[i][0]] + AB[i][1] == dp[i+1][j]:
        used[i] = True
        j -= AB[i][0]
        #print("j =", j)
    
#print(used)

last = 0
for i in range(N):
    if not used[i]:
        last = max(last, AB[i][1])

print(dp[-1][-1] + last)

#print(dp)

Buggy submission (verdict: Runtime Error):

N, T = map(int, input().split())

AB = [tuple(map(int, input().split())) for _ in range(N)]


AB.sort()

dp = [[0 for _ in range(T)] for _ in range(N+1)]




for i in range(N):
    for j in range(T):
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1] )


# 使ってないものを探す

used = [False] * N
j = T-1
#print("j =", j)
for i in reversed(range(N)):
    if dp[i+1][j] == 0 or dp[i][j] == 0:
        break
    #for j in reversed(range(T)):
    # i を使う場合
    #print(i, dp[i][j - AB[i][0]] + AB[i][1] , dp[i][j])
    #print("i, j, dp(i+1,j), dp[i+1][j - AB[i][0]] + AB[i][1] ", i, j, dp[i+1][j], dp[i+1][j - AB[i][0]] + AB[i][1] )
    #print(i,j, AB[i][0])
    if dp[i][j - AB[i][0]] + AB[i][1] == dp[i+1][j]:
        used[i] = True
        j -= AB[i][0]
        #print("j =", j)
    
#print(used)

last = 0
for i in range(N):
    if not used[i]:
        last = max(last, AB[i][1])

print(dp[-1][-1] + last)

#print(dp)

Buggy submission (verdict: Runtime Error):

N, T = map(int, input().split())

AB = [tuple(map(int, input().split())) for _ in range(N)]


AB.sort()

dp = [[0 for _ in range(T)] for _ in range(N+1)]




for i in range(N):
    for j in range(T):
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1] )


# 使ってないものを探す

used = [False] * N
j = T-1
#print("j =", j)
for i in reversed(range(N)):
    if j < 0 or dp[i+1][j] == 0:
        break
    #for j in reversed(range(T)):
    # i を使う場合
    #print(i, dp[i][j - AB[i][0]] + AB[i][1] , dp[i][j])
    #print("i, j, dp(i+1,j), dp[i+1][j - AB[i][0]] + AB[i][1] ", i, j, dp[i+1][j], dp[i+1][j - AB[i][0]] + AB[i][1] )
    if dp[i][j - AB[i][0]] + AB[i][1] == dp[i+1][j]:
        used[i] = True
        j -= AB[i][0]
        #print("j =", j)
    
#print(used)

last = 0
for i in range(N):
    if not used[i]:
        last = max(last, AB[i][1])

print(dp[-1][-1] + last)

#print(dp)

Buggy submission (verdict: Runtime Error):

N, T = map(int, input().split())

AB = [tuple(map(int, input().split())) for _ in range(N)]


AB.sort()

dp = [[0 for _ in range(T)] for _ in range(N+1)]




for i in range(N):
    for j in range(T):
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1] )


# 使ってないものを探す

used = [False] * N
j = T-1
#print("j =", j)
for i in reversed(range(N)):
    if j < 0 or dp[i+1][j] == 0:
        break
    #for j in reversed(range(T)):
    # i を使う場合
    #print(i, dp[i][j - AB[i][0]] + AB[i][1] , dp[i][j])
    #print("i, j, dp(i+1,j), dp[i+1][j - AB[i][0]] + AB[i][1] ", i, j, dp[i+1][j], dp[i+1][j - AB[i][0]] + AB[i][1] )
    if dp[i][j - AB[i][0]] + AB[i][1] == dp[i+1][j]:
        used[i] = True
        j -= AB[i][0]
        #print("j =", j)
    
#print(used)

last = 0
for i in range(N):
    if not used[i]:
        last = max(last, AB[i][1])

print(dp[N][-1] + last)

#print(dp)

Buggy submission (verdict: Runtime Error):

N, T = map(int, input().split())

AB = [tuple(map(int, input().split())) for _ in range(N)]


AB.sort()

dp = [[0 for _ in range(T)] for _ in range(N+1)]




for i in range(N):
    for j in range(T):
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1] )


# 使ってないものを探す

used = [False] * N
j = T-1
#print("j =", j)
for i in reversed(range(N)):
    if j < 0 or dp[i+1][j] == 0:
        break
    #for j in reversed(range(T)):
    # i を使う場合
    #print(i, dp[i][j - AB[i][0]] + AB[i][1] , dp[i][j])
    #print("i, j, dp(i+1,j), dp[i+1][j - AB[i][0]] + AB[i][1] ", i, j, dp[i+1][j], dp[i+1][j - AB[i][0]] + AB[i][1] )
    if dp[i][j - AB[i][0]] + AB[i][1] == dp[i+1][j]:
        used[i] = True
        j -= AB[i][0]
        #print("j =", j)
    
#print(used)

last = 0
for i in range(N):
    if not used[i]:
        last = max(last, AB[i][1])

print(dp[N][-1] + last)

#print(dp)

Buggy submission (verdict: Runtime Error):

N, T = map(int, input().split())

AB = [tuple(map(int, input().split())) for _ in range(N)]


AB.sort()

dp = [[0 for _ in range(T)] for _ in range(N+1)]




for i in range(N):
    for j in range(T):
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1] )


# 使ってないものを探す

used = [False] * N
j = T-1
#print("j =", j)
for i in reversed(range(N)):
    if dp[i+1][j] == 0:
        break
    #for j in reversed(range(T)):
    # i を使う場合
    #print(i, dp[i][j - AB[i][0]] + AB[i][1] , dp[i][j])
    #print("i, j, dp(i+1,j), dp[i+1][j - AB[i][0]] + AB[i][1] ", i, j, dp[i+1][j], dp[i+1][j - AB[i][0]] + AB[i][1] )
    if dp[i][j - AB[i][0]] + AB[i][1] == dp[i+1][j]:
        used[i] = True
        j -= AB[i][0]
        #print("j =", j)
    
#print(used)

last = 0
for i in range(N):
    if not used[i]:
        last = max(last, AB[i][1])

print(dp[N][-1] + last)

#print(dp)

Buggy submission (verdict: Runtime Error):

N, T = map(int, input().split())

AB = [tuple(map(int, input().split())) for _ in range(N)]


AB.sort()

dp = [[0 for _ in range(T)] for _ in range(N+1)]




for i in range(N):
    for j in range(T):
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1] )


# 使ってないものを探す

used = [False] * N
j = T-1
#print("j =", j)
for i in reversed(range(N)):
    if dp[i+1][j] == 0:
        break
    #for j in reversed(range(T)):
    # i を使う場合
    #print(i, dp[i][j - AB[i][0]] + AB[i][1] , dp[i][j])
    #print("i, j, dp(i+1,j), dp[i+1][j - AB[i][0]] + AB[i][1] ", i, j, dp[i+1][j], dp[i+1][j - AB[i][0]] + AB[i][1] )
    if dp[i][j - AB[i][0]] + AB[i][1] == dp[i+1][j]:
        used[i] = True
        j -= AB[i][0]
        #print("j =", j)
    
#print(used)

last = 0
for i in range(N):
    if not used[i]:
        last = max(last, AB[i][1])

print(dp[N][-1] + last)

#print(dp)