Problem p02863 (python)

Fixed submission:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,w = inpl()
wv = [inpl() for i in range(n)]
dp = [[0 for i in range(w+1)] for j in range(n+1)]
wv.sort()
wv.sort(key=lambda x:x[1])
ww = [0] * n
vv = [0] * n
for i in range(n):
    ww[i],vv[i] = wv[i][0], wv[i][1]
for i in range(n-1):
    for j in range(w+1):
        if j >= ww[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-ww[i]]+vv[i])
        else:
            dp[i+1][j] = dp[i][j]
res = dp[n-1][w-1]+wv[n-1][1]

dp = [[0 for i in range(w+1)] for j in range(n+1)]
ww[-1],ww[-2] = ww[-2],ww[-1]
vv[-1],vv[-2] = vv[-2],vv[-1]
for i in range(n-1):
    for j in range(w+1):
        if j >= ww[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-ww[i]]+vv[i])
        else:
            dp[i+1][j] = dp[i][j]
print(max(res,dp[n-1][w-1]+vv[n-1]))

Buggy submission (verdict: Runtime Error):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,t = inpl()
wv = [inpl() for _ in range(n)]
rwv = wv[::-1]
udp = [[0] * t for _ in range(n+5)]
ddp = [[0] * t for _ in range(n+5)]

for i in range(n-1):
    w,v = wv[i]
    for j in range(t):
        if j < w:
            udp[i+1][j] = udp[i][j]
        else:
            udp[i+1][j] = max(udp[i][j], udp[i][j-w] + v)
res = udp[n-1][t-1] + wv[n-1][1]

for i in range(n-1):
    w,v = rwv[i]
    for j in range(t):
        if j < w:
            ddp[i+1][j] = ddp[i][j]
        else:
            ddp[i+1][j] = max(ddp[i][j], ddp[i][j-w] + v)
    res = max(res,ddp[n-1][t-1] + wv[0][1])

for i in range(1,n-1):
    u = i; d = n-i-1
    mx = 0
    for j in range(t):
        tmp = udp[u][j] + ddp[d][n-1-j]
        mx = max(mx, tmp)
    res = max(res, mx)
print(res)

Buggy submission (verdict: Runtime Error):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,t = inpl()
wv = [inpl() for _ in range(n)]
rwv = wv[::-1]
udp = [[0] * t for _ in range(n)]
ddp = [[0] * t for _ in range(n)]

for i in range(n-1):
    w,v = wv[i]
    for j in range(t):
        if j < w:
            udp[i+1][j] = udp[i][j]
        else:
            udp[i+1][j] = max(udp[i][j], udp[i][j-w] + v)
res = udp[n-1][t-1] + wv[n-1][1]

for i in range(n-1):
    w,v = rwv[i]
    for j in range(t):
        if j < w:
            ddp[i+1][j] = ddp[i][j]
        else:
            ddp[i+1][j] = max(ddp[i][j], ddp[i][j-w] + v)
    res = max(res,ddp[n-1][t-1] + wv[0][1])

for i in range(1,n-1):
    u = i; d = n-i-1
    mx = 0
    for j in range(t):
        tmp = udp[u][j] + ddp[d][n-1-j]
        mx = max(mx, tmp)
    res = max(res, mx)
print(res)

Buggy submission (verdict: Runtime Error):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,t = inpl()
wv = [inpl() for _ in range(n)]
rwv = wv[::-1]
# print(rwv)
udp = [[0] * t for _ in range(n)]
ddp = [[0] * t for _ in range(n)]

for i in range(n-1):
    w,v = wv[i]
    for j in range(t):
        if j < w:
            udp[i+1][j] = udp[i][j]
        else:
            udp[i+1][j] = max(udp[i][j], udp[i][j-w] + v)
res = udp[n-1][t-1] + wv[n-1][1]

for i in range(n-1):
    w,v = rwv[i]
    for j in range(t):
        if j < w:
            ddp[i+1][j] = ddp[i][j]
        else:
            ddp[i+1][j] = max(ddp[i][j], ddp[i][j-w] + v)
    res = max(res,ddp[n-1][t-1] + wv[0][1])

for i in range(1,n-2):
    u = i; d = n-i-2
    mx = 0
    for j in range(t):
        tmp = udp[u][j] + ddp[d][n-1-j]
        mx = max(mx, tmp)
    res = max(res, mx)
print(res)

Buggy submission (verdict: Runtime Error):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,t = inpl()
wv = [inpl() for _ in range(n)]
udp = [[0] * t for _ in range(n)]
ddp = [[0] * t for _ in range(n)]

for i in range(n-1):
    w,v = wv[i]
    for j in range(t):
        if j < w:
            udp[i+1][j] = udp[i][j]
        else:
            udp[i+1][j] = max(udp[i][j], udp[i][j-w] + v)
res = udp[n-1][t-1] + wv[n-1][1]

for i in range(n-1):
    w,v = wv[n-1-i]
    for j in range(t):
        if j < w:
            ddp[i+1][j] = ddp[i][j]
        else:
            ddp[i+1][j] = max(ddp[i][j], ddp[i][j-w] + v)
    res = max(res,ddp[n-1][t-1] + wv[0][1])

for i in range(1,n-1):
    u = i; d = n-i-2
    mx = 0
    for j in range(t):
        tmp = udp[u][j] + ddp[d][n-1-j]
        mx = max(mx, tmp)
    res = max(res, mx)
print(res)