Problem p02863 (python)

Fixed submission:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
# MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
# import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
# from math import gcd
# from fractions import gcd
# from collections import deque
# from collections import defaultdict
# from collections import Counter
# from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())

def knapsack(N, W, weight, value):
	# 初期化
	inf = float("inf")
	dp = [[-inf for i in range(W + 1)] for j in range(N + 1)]
	for i in range(W + 1): dp[0][i] = 0
	
	# DP
	for i in range(N):
		for w in range(W + 1):
			if weight[i] <= w:  # dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
				dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w])
			else:  # 入る可能性はない
				dp[i + 1][w] = dp[i][w]
	return dp


def main():
	n, t = map(int, input().split())
	AB = []
	A = []
	B = []
	for _ in range(n):
		a, b = map(int, input().split())
		AB.append((a, b))
	AB.sort()
	for a,b in AB:
		A.append(a)
		B.append(b)
	dp= knapsack(n, t, A, B)
	
	ans=0
	for i in range(n):
		ans=max(ans,dp[i][t-1] + AB[i][1])
	print(ans)


if __name__ == '__main__':
	main()

Buggy submission (verdict: Runtime Error):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
# MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
# import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
# from math import gcd
# from fractions import gcd
# from collections import deque
# from collections import defaultdict
# from collections import Counter
# from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


# 枝刈り探索（分枝限定法）

class Knapsack:
	def __init__(self, VW):
		self.VW = VW
		self.VW.sort(key=lambda vw: vw[0] / vw[1], reverse=True)
		self.n = len(VW)
	
	def solve(self, capacity, ok=0):
		self.ok = ok
		self.capacity = capacity
		return self._dfs(0, 0, 0)
	
	def _dfs(self, i, v_now, w_now):
		if i == self.n:
			self.ok = max(self.ok, v_now)
			return v_now
		ng, f = self._solve_relaxation(i, self.capacity - w_now)
		ng += v_now
		if f:
			self.ok = max(self.ok, ng)
			return ng
		if ng < self.ok:
			return -float("inf")
		res = -float("inf")
		v, w = self.VW[i]
		if w_now + w <= self.capacity:
			res = max(res, self._dfs(i + 1, v_now + v, w_now + w))
		res = max(res, self._dfs(i + 1, v_now, w_now))
		return res
	
	def _solve_relaxation(self, i, capacity):
		res = 0
		f = True
		for v, w in self.VW[i:]:
			if capacity == 0:
				break
			if w <= capacity:
				capacity -= w
				res += v
			else:
				f = False
				res += v * (capacity / w)
				break
		return res, f


def main():
	n, t = map(int, input().split())
	AB=[]
	for _ in range(n):
		A,B = map(int, input().split())
		AB.append((B,A))
	AB.sort()
	knapsack = Knapsack(AB[:-1])
	ans = knapsack.solve(t-1) + AB[-1][0]
	print(ans)


if __name__ == '__main__':
	main()

Buggy submission (verdict: Runtime Error):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# rstrip().decode('utf-8')
# INF=float("inf")
# MOD=10**9+7
# sys.setrecursionlimit(2147483647)
# import math
# import numpy as np
# import operator
# import bisect
# from heapq import heapify,heappop,heappush
# from math import gcd
# from fractions import gcd
# from collections import deque
# from collections import defaultdict
# from collections import Counter
# from itertools import accumulate
# from itertools import groupby
# from itertools import permutations
# from itertools import combinations
# from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
# from scipy.sparse.csgraph import csgraph_from_dense
# from scipy.sparse.csgraph import dijkstra
# map(int,input().split())


# 枝刈り探索（分枝限定法）

class Knapsack:
	def __init__(self, VW):
		self.VW = VW
		self.VW.sort(key=lambda vw: vw[0] / vw[1], reverse=True)
		self.n = len(VW)
	
	def solve(self, capacity, ok=0):
		self.ok = ok
		self.capacity = capacity
		return self._dfs(0, 0, 0)
	
	def _dfs(self, i, v_now, w_now):
		if i == self.n:
			self.ok = max(self.ok, v_now)
			return v_now
		ng, f = self._solve_relaxation(i, self.capacity - w_now)
		ng += v_now
		if f:
			self.ok = max(self.ok, ng)
			return ng
		if ng < self.ok:
			return -float("inf")
		res = -float("inf")
		v, w = self.VW[i]
		if w_now + w <= self.capacity:
			res = max(res, self._dfs(i + 1, v_now + v, w_now + w))
		res = max(res, self._dfs(i + 1, v_now, w_now))
		return res
	
	def _solve_relaxation(self, i, capacity):
		res = 0
		f = True
		for v, w in self.VW[i:]:
			if capacity == 0:
				break
			if w <= capacity:
				capacity -= w
				res += v
			else:
				f = False
				res += v * (capacity / w)
				break
		return res, f


def main():
	n, t = map(int, input().split())
	AB=[]
	for _ in range(n):
		A,B = map(int, input().split())
		AB.append((B,A))
	AB.sort()
	knapsack = Knapsack(AB[:-1])
	ans = knapsack.solve(t-1) + AB[-1][0]
	print(ans)


if __name__ == '__main__':
	main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')
#INF=float("inf")
#MOD=10**9+7
#sys.setrecursionlimit(2147483647)
#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#map(int,input().split())


# 枝刈り探索（分枝限定法）

class Knapsack:
	def __init__(self, VW):
		self.VW = VW
		self.VW.sort(key=lambda vw: vw[0] / vw[1], reverse=True)
		self.n = len(VW)
	
	def solve(self, capacity, ok=0):
		self.ok = ok
		self.capacity = capacity
		return self._dfs(0, 0, 0)
	
	def _dfs(self, i, v_now, w_now):
		if i == self.n:
			self.ok = max(self.ok, v_now)
			return v_now
		ng, f = self._solve_relaxation(i, self.capacity - w_now)
		ng += v_now
		if f:
			self.ok = max(self.ok, ng)
			return ng
		if ng < self.ok:
			return -float("inf")
		res = -float("inf")
		v, w = self.VW[i]
		if w_now + w <= self.capacity:
			res = max(res, self._dfs(i + 1, v_now + v, w_now + w))
		res = max(res, self._dfs(i + 1, v_now, w_now))
		return res
	
	def _solve_relaxation(self, i, capacity):
		res = 0
		f = True
		for v, w in self.VW[i:]:
			if capacity == 0:
				break
			if w <= capacity:
				capacity -= w
				res += v
			else:
				f = False
				res += v * (capacity / w)
				break
		return res, f

def main():
	n,t=map(int,input().split())
	AB = [list(map(int, input().split())) for _ in range(n)]
	AB.sort(key=lambda x:x[1],reverse=True)
	knapsack = Knapsack(AB)
	ans=knapsack.solve(t-1)+AB[-1][1]
	print(ans)
	
	
	

	
	
if __name__ == '__main__':
	main()

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')
INF=float("inf")
MOD=10**9+7
#sys.setrecursionlimit(2147483647)
#import math
import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#map(int,input().split())


# 枝刈り探索（分枝限定法）

class Knapsack:
	def __init__(self, VW):
		self.VW = VW
		self.VW.sort(key=lambda vw: vw[0] / vw[1], reverse=True)
		self.n = len(VW)
	
	def solve(self, capacity, ok=0):
		self.ok = ok
		self.capacity = capacity
		return self._dfs(0, 0, 0)
	
	def _dfs(self, i, v_now, w_now):
		if i == self.n:
			self.ok = max(self.ok, v_now)
			return v_now
		ng, f = self._solve_relaxation(i, self.capacity - w_now)
		ng += v_now
		if f:
			self.ok = max(self.ok, ng)
			return ng
		if ng < self.ok:
			return -float("inf")
		res = -float("inf")
		v, w = self.VW[i]
		if w_now + w <= self.capacity:
			res = max(res, self._dfs(i + 1, v_now + v, w_now + w))
		res = max(res, self._dfs(i + 1, v_now, w_now))
		return res
	
	def _solve_relaxation(self, i, capacity):
		res = 0
		f = True
		for v, w in self.VW[i:]:
			if capacity == 0:
				break
			if w <= capacity:
				capacity -= w
				res += v
			else:
				f = False
				res += v * (capacity / w)
				break
		return res, f

def main():
	n,t=map(int,input().split())
	AB = [list(map(int, input().split())) for _ in range(n)]
	AB.sort(key=lambda x:x[1],reverse=True)
	knapsack = Knapsack(AB)
	ans=knapsack.solve(t-1)+AB[-1][1]
	print(ans)
	
	
	

	
	
if __name__ == '__main__':
	main()