Problem:


Score : 500 points

Problem Statement

Takahashi is at an all-you-can-eat restaurant.

The restaurant offers N kinds of dishes. It takes A_i minutes to eat the i-th dish, whose deliciousness is B_i.

The restaurant has the following rules:

You can only order one dish at a time. The dish ordered will be immediately served and ready to eat.

You cannot order the same kind of dish more than once.

Until you finish eating the dish already served, you cannot order a new dish.

After T-0.5 minutes from the first order, you can no longer place a new order, but you can continue eating the dish already served.

Let Takahashi's happiness be the sum of the deliciousness of the dishes he eats in this restaurant.

What is the maximum possible happiness achieved by making optimal choices?

Constraints

2 \leq N \leq 3000

1 \leq T \leq 3000

1 \leq A_i \leq 3000

1 \leq B_i \leq 3000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N T
A_1 B_1
:
A_N B_N

Output

Print the maximum possible happiness Takahashi can achieve.

Sample Input 1

2 60
10 10
100 100

Sample Output 1

110

By ordering the first and second dishes in this order, Takahashi's happiness will be 110.

Note that, if we manage to order a dish in time, we can spend any amount of time to eat it.

Sample Input 2

3 60
10 10
10 20
10 30

Sample Output 2

60

Takahashi can eat all the dishes within 60 minutes.

Sample Input 3

3 60
30 10
30 20
30 30

Sample Output 3

50

By ordering the second and third dishes in this order, Takahashi's happiness will be 50.

We cannot order three dishes, in whatever order we place them.

Sample Input 4

10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25

Sample Output 4

145



Sample input:
2 60
10 10
100 100


Sample output:
110

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, T = list(map(int, sys.stdin.readline().split()))
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

AB.sort()

ans = 0
dp = np.zeros(T, dtype=int)
for a, b in AB:
    ans = max(ans, dp.max() + b)
    np.maximum(dp[:-a] + b, dp[a:], out=dp[a:])
print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, t = na()
dp = [0] * 6005
ab = []
for i in range(n):
    ab.append(na())

ab.sort(key=lambda x: x[0])
for u in ab:
    for i in range(6004-u[0], -1, -1):
        if i < t:
            dp[i+u[0]] = max(dp[i+u[0]], dp[i] + u[1])

print(max(dp))

Submission status: Runtime Error

Solution code:
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

@njit((i8,i8,i8[:,:]), cache=True)
def main(N,T,A):
  dp = np.zeros(T+1,np.int64)
  for a,b in A:
    for t in range(T-1,-1,-1):
      u = min(T,t+a)
      dp[u] = max(dp[u],dp[t]+b)
  ans = dp[-1]
  return ans

N, T = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
A = np.array(sorted(A))
print(main(N,T,A))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n, t = map(int, input().split())
    dp = np.zeros(t,dtype=int)
    food = []
    for _ in range(n):
        a, b = map(int, input().split())
        food.append([a, b])
    food.sort(key=lambda x: x[0]*-1)
    for j in range(n):
        a, b = food[j][0], food[j][1]
        dptmp=np.zeros(t,dtype=int)
        dptmp[a:] = np.maximum(dp[a:],dp[:-a]+b)
        dptmp[:a] = np.maximum(np.full(a,b,dtype=int), dp[:a])
        dp=dptmp
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import permutations
class Food:
  def __init__(self, time, satisfaction):
    self.time = time
    self.satisfaction = satisfaction 
N, T = map(int, input().split())

foods =[]
for n in range(N):
  t,s = map(int, input().split())
  foods.append(Food(t,s))

orders = list(permutations(foods))

satisfactions = []
for order in orders:
  satisfy = 0
  time = 0
  i = 0
  while time < T:
    if time >= T:
      break
    else:
      satisfy += order[i].satisfaction
      i += 1
      time += order[i].time
  satisfactions.append(satisfy)

print(max(satisfactions))

Submission status: Runtime Error

Solution code:
n,t=list(map(int,input().split()))
ab=sorted([list(map(int,input().split())) for _ in range(n)],key=lambda x: 10000*x[1]+x[0])

a,b=ab.pop()
ans2=b
t-=1

dp=[[-10**10]*3001 for _ in range(n+1)]
dp[0][0]=0

bmax=0
for i in range(n-1):
    for j in range(t+1):
        dp[i+1][j]=max(dp[i][j],dp[i][j-ab[i][0]]+ab[i][1] if j>=ab[i][0] else 0)
        bmax=max(bmax,dp[i+1][j])

ans2+=bmax

print(max(ans,ans2))

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, T, *AB = map(int, read().split())
    A = AB[::2]
    B = AB[1::2]

    dp = [[0] * T for _ in range(N + 1)]
    for i in range(N):
        for t in range(T):
            if 0 <= t - A[i]:
                dp[i + 1][t] = dp[i][t - A[i]] + B[i]
            if dp[i + 1][t] < dp[i][t]:
                dp[i + 1][t] = dp[i][t]

    C = [False] * N

    t = T - 1
    for i in range(N - 1, -1, -1):
        if dp[i + 1][t] == dp[i][t - A[i]] + B[i]:
            C[i] = True
            t -= A[i]

    ans = dp[N][T - 1] + max((B[i] for i in range(N) if not C[i]), default=0)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")


N, T = map(int, f.readline().split())
ab = [list(map(int, f.readline().split())) for _ in range(N)]

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

ab = sorted(ab, key = lambda x: x[0])

for i in range(N-1):
    for j in range(T-1,-1, -1):
        if j+ab[i][0] <= T-1:
            kari2 = Dp[j] + ab[i][1]
            if  Dp[j+ab[i][0]] < kari2:
                Dp[j+ab[i][0]] = kari2
        else:
            kari2 = Dp[j] +ab[i][1]
            if Dp[T] < kari2:
                Dp[T] = kari2
                
print(max(Dp))

Submission status: Runtime Error

Solution code:
f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")


N, T = map(int, f.readline().split())
ab = [list(map(int, f.readline().split())) for _ in range(N)]

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

ab = sorted(ab, key = lambda x: x[0])

for i in range(N-1):
    for j in range(T-1,-1, -1):
        if j+ab[i][0] <= T-1:
            kari2 = Dp[j] + ab[i][1]
            if  Dp[j+ab[i][0]] < kari2:
                Dp[j+ab[i][0]] = kari2
print(Dp[T-1]+ab[-1][1])

Submission status: Runtime Error

Solution code:
def function():
    N, T = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    
    Dp = [0 for _ in range(T+1)]
    used_ab = [set() for _ in range(T+1)]
    
    
    for i in range(N):
        for j in range(T-1,-1, -1):
            if j+AB[i][0] <= T-1:
                kari1 = Dp[j+AB[i][0]]
                kari2 = Dp[j] + AB[i][1]
                if  kari1< kari2:
                    Dp[j+AB[i][0]] = kari2
                    kari = used_ab[j].copy()
                    kari.add(i)
                    used_ab[j+AB[i][0]] = kari
    
    answer = 0
    for i in range(T):
        max_amari = 0
        for j in range(N):
            if j not in used_ab[i] and max_amari < AB[j][1]:
                max_amari = AB[j][1]
        if Dp[i]+max_amari > answer:
            answer = Dp[i]+max_amari
    
    print(answer)
    
if __name__ = "__main__":
    function()

Submission status: Runtime Error

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, T = rl()
A, B = [], []
for i in range(N):
	a, b = rl()
	A.append(a)
	B.append(b)

eaten = [0] * N
def dfs(t):
	if t <= 0:
		return 0
	max_b = 0
	for i in range(N):
		if eaten[i] == 1:
			continue
		eaten[i] = 1
		b = dfs(t-A[i]) + B[i]
		max_b = max(max_b, b)
		eaten[i] = 0
	return max_b

print(dfs(T))

Submission status: Runtime Error

Solution code:
from itertools import accumulate

n,t = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
dp1 = [[-(10 ** 18)] * t for i in range(n)]
dp2 = [[-(10 ** 18)] * t for i in range(n)]
dp1[0][0] = 0
dp2[0][0] = 0
for i,(a,b) in enumerate(ab[:-1]):
  for j in range(t-a):
    dp1[i+1][j] = max(dp1[i+1][j],dp1[i][j])
    dp1[i+1][j+a] = max(dp1[i+1][j+a],dp1[i][j]+b)
  for j in range(t-a,t):
    dp1[i+1][j] = max(dp1[i+1][j],dp1[i][j])
for i,(a,b) in enumerate(ab[n-1:0:-1]):
  for j in range(t-a):
    dp2[i+1][j] = max(dp2[i+1][j],dp2[i][j])
    dp2[i+1][j+a] = max(dp2[i+1][j+a],dp2[i][j]+b)
  for j in range(t-a,t):
    dp2[i+1][j] = max(dp2[i+1][j],dp2[i][j])
ans = 0
for key,(i,j,(a,b)) in enumerate(zip(dp1,dp2[::-1],ab)):
  nowi,nowj = 0,0
  I,J = [],[]
  for x,y in zip(i,j):
    nowi = max(nowi,x)
    nowj = max(nowj,y)
    I.append(nowi)
    J.append(nowj)
  J.reverse()
  tmp = 0
  for x,y in zip(I,J):
    tmp = max(tmp,x+y)
  tmp += b
  ans = max(ans,tmp)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N,T = map(int,input().split())
DP=[[0 for a in range(T+1)] for c in range(N)]
A0,B0 = map(int,input().split())
DP[0][A0]=B0
b=B0
for i in range(1,N):
 A,B = map(int,input().split())
 DP[i][T]=b+B
 b=0
 for j in range(T):
  if j>=A:
   DP[i][j]=max(DP[i-1][j],DP[i-1][j-A]+B)
  else:
   DP[i][j]=DP[i-1][j]
  b=max(b,DP[i][j])
print(DP[N-1][T])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N,T = map(int,input().split())
DP=[[0 for a in range(T+1)] for b in range(N)]
A0,B0 = map(int,input().split())
DP[0][A0]=B0
b=B0
for i in range(1,N):
 A,B = map(int,input().split())
 DP[i][T]=b+B
 b=0
 for j in range(T):
  if j>=A:
   DP[i][j]=max(DP[i-1][j],DP[i-1][j-A]+B)
  else:
   DP[i][j]=DP[i-1][j]
  b=max(b,DP[i][j])
print(DP[N-1][T])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N,T = map(int,input().split())
DP=[[0 for a in range(T+30)] for b in range(N)]
A0,B0 = map(int,input().split())
DP[0][A0]=B0
for i in range(1,N):
 A,B = map(int,input().split())
 for j in range(T):
  if j>=A:
   DP[i][j]=max(DP[i-1][j],DP[i-1][j-A]+B)
  else:
   DP[i][j]=DP[i-1][j]
 for m in range(T,T+30):
  if m-A<=T-1:
   DP[i][m]=max(DP[i-1][m],DP[i-1][m-A]+B)
  else:
   DP[i][m]=DP[i-1][m]
c=0
for k in range(T,T+30):
 c=max(c,DP[N-1][k])
print(c)

Submission status: Runtime Error

Solution code:
from collections import*

d=defaultdict(list)
n,t=map(int,input().split())

x=[list(map(int,input().split()))+[i]for i in range(n)]

d[0]=[0,[]]
for time,value,idx in x:
    for k,v in d.copy().items():
        if k+time<=t:
            if len(d[k+time])==2:
                if v[0]+value>d[k+time][0]:
                    d[k+time]=[v[0]+value,v[1]+[idx]]
            else:
                d[k+time]=[v[0]+value,v[1]+[idx]]



y,z=d[max(d.keys())]

for i in z[::-1]:
    del x[i]
    
print(y+max(i[1] for i in x))

Submission status: Runtime Error

Solution code:
N, T = map(int, input().split())

dises = sorted([tuple(map(int,input().split())) for i in range(N)])

dp = [[0] * 3100 for _ in range(3100)]

for i in range(1, N + 1):
    for j in range(1, T):
#dpをもとにした最大値の更新
        dp[i][j] = dp[i-1][j] 
        ans = max(ans, dp[i][j] + dishes[i-1][1]) #最後に、最も時間のかかるものを食べて、大きい場合は最大値（ans）を更新

# dpの更新
        if j - dishes[i-1][0] >= 0: #最後に食べる品が持ち時間より長いばあいはNG
            dp[i][j] = max(dp[i][j], dp[i-1][j-dishes[i-1][0]] + dishes[i-1][1]) #ラストオーダーまでにj-dishes[i-1][0]の時間があるので

print(ans)

Submission status: Runtime Error

Solution code:
# E - All-you-can-eat
n,t=map(int,input().split())
a,b=[],[]
for i in range(n):
    aa,bb=map(int,input().split())
    a.append(aa)
    b.append(bb)

dp=[[0]*(2*t+1) for i in range(n+1)]

for i in range(n):
    for j in range(1,2*t+1):
        # if j-a[i]>=0:
        #     dp[i+1][j]=max(dp[i+1][j],dp[i][j-a[i]]+b[i])
        # dp[i+1][j]=max(dp[i+1][j],dp[i][j])
        if j-a[i]>=0:
            dp[i+1][j]=max(dp[i+1][j],dp[i][j-a[i]]+b[i])
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
# print(dp)
# print(dp[10][124])
a_max=max(a)
ans=0
if t+a_max-1>2*t:
    print(dp[n][sum(a)])
    exit()

for i in range(t-a_max-1,t+a_max-2):
    ans=max(dp[n][i],ans)

print(ans)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

ans = 0

DP = [0] * T

for i in range(N):
  a, b = AB[i]
  for j in range(T - 1, -1, -1):
    if j + a >= T:
      ans = max(ans, DP[j] + b)
    else:
      DP[j + a] = max(DP[j + a], DP[j] + b)

for i in range(N):
  ans = max(ans, DP[i])
print(ans)

Submission status: Runtime Error

Solution code:
n,t = map(int,input().split())
ab = [[0,0] for _ in range(n)]
for i in range(n):
    ab[i] = list(map(int,input().split()))
dp = [[0]*t for i in range(n+1)]
ab.sort()
ans = 0
for i in range(n):
    a,b = ab[i]
    for j in range(t)[::-1]:
        v = dp[i][j]
        ans = max(ans,v+b)
        dp[i+1][j] = max(dp[i+1][j], dp[j][i])
        if j + a >= t:continue
        dp[i+1][j+a] = max(dp[i][j+a], v+b)
print(ans)

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

Solution code:
mod = 10**9 + 7
def iip(listed = False):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def inv(n, mod):
    return power(n, mod-2)

def conbination(n, r, mod, test=False):
    if n <=0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0

    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    #if test:
    #    print(f"{n}C{r} = {ret}")
    return ret

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


#########################入力受付部
N, T = iip()
AB = []
A = []
B = []
for i in range(N):
    a, b = iip()
    AB.append((a, b))
    AB = sorted(AB, key=lambda x:x[1])

#########################入力受付部

def main():
    manzoku_list = [0 for i in range(T)]
    tabeta_list = [[] for i in range(T)]

    for i, ab in enumerate(AB):
        a = ab[0]
        b = ab[1]
        #print(a, b)
        manzoku_list2 = [i for i in manzoku_list]
        tabeta_list2 = [i for i in tabeta_list]
        for j, manzoku in enumerate(manzoku_list2):
            if not j+a >= T:
                if manzoku_list2[j+a] < manzoku+b:
                    manzoku_list[j+a] = manzoku+b
                    tabeta_list[j+a] = list([*tabeta_list2[j], i])
        #print(tabeta_list)

    maxx = 0
    for i, ab in enumerate(AB):
        if not i in tabeta_list[T-1]:
            maxx = max(ab[1], maxx)


    ans = manzoku_list[T-1] + maxx

    #print(tabeta_list)
    #print(manzoku_list)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
from copy import deepcopy
# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans


N, T = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort()

ans = 0
dp = make_multi_list(0, [3000, 3000])
for i in range(N):
    a, b = AB[i]
    for j in range(T):
        # iを使わないパターン
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        # iを使うパターン
        nj = j+a
        if nj < T:
            dp[i+1][nj] = max(dp[i + 1][nj], dp[i][j]+b)
    now = dp[i][T-1]+AB[i][1]
    ans = max(ans, now)

print(ans)

Submission status: Runtime Error

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, T = MAP()
L = [LIST() for i in range(N)]

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

L.sort()
for i in range(N):
    for j in range(T):
        if j - L[i][1] >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-L[i][0]]+L[i][1])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
# print(dp[N][T-1])

ans = 0
for k in range(N):
    # k番目を食べずにk-1番目まで食べたT-1秒以下での最大値に，
    # k番目のものをT-1秒目に食べた値の中での最大値
    # 一番いいものを最後に食べる
    ans = max(dp[k][T-1] + L[k][1], ans)
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MOD 1000000007
#define INF 800000000
#define MAX 1000

int main(){
  int N,T;
  cin>>N>>T;
  vector<int> A(N),B(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i)>>B.at(i);
  }

  vector<int> dp(6001,0);
  for(int i=0;i<N;i++){
    for(int j=6000;j>=0;j--){
      if(0<=j-A.at(i)&&j-A.at(i)<T){
        dp.at(j)=max(dp.at(j),dp.at(j-A.at(i))+B.at(i));
      }
    }
  }
  int ans=0;
  for(int i=0;i<=6000;i++){
    ans=max(ans,dp.at(i));
  }
  cout<<ans<<endl;
}

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N, T = map(int, input().rstrip().split())
AB = [list(map(int, input().rstrip().split())) for _ in range(N)]
AB = sorted(AB, key=lambda x: x[0])

dp = [0] * (T + 30001)

def dfs(i, t, v):
    if i >= N:
        return v
    if t >= T:
        return v
       
    if dp[t+AB[i][0]] < v + AB[i][1]:
        dp[t+AB[i][0]] = v + AB[i][1]
        dfs(i + 1, t + AB[i][0], dp[t+AB[i][0]])

    dfs(i + 1, t, v)  
        
    return 0
    
dfs(0, 0, 0)
print(max(dp))

Submission status: Runtime Error

Solution code:
N, T = map(int, input().rstrip().split())
AB = [list(map(int, input().rstrip().split())) for _ in range(N)]
AB = sorted(AB, key=lambda x: x[0])

dp = [0] * (T + 3001)

def dfs(i, t, v):
    if i >= N:
        return v
    if t >= T:
        return v
    
    if dp[t+AB[i][0]] < v + AB[i][1]:
        dp[t+AB[i][0]] = v + AB[i][1]
        dfs(i + 1, t + AB[i][0], dp[t+AB[i][0]])
    dfs(i + 1, t, v)  
        
    return 0
    
dfs(0, 0, 0)
print(max(dp))

Submission status: Runtime Error

Solution code:
import numpy as np


def read():
    N, T = list(map(int, input().strip().split()))
    A = list()
    B = list()
    for i in range(N):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        B.append(b)
    return N, T, A, B

def solve(N, T, A, B):
    dp1 = [[0 for j in range(T)] for i in range(N+2)]
    dp2 = [[0 for j in range(T)] for i in range(N+2)]
    for i in range(1, N+1, 1):
        for t in range(T):
            if A[i-1] <= t:
                dp1[i][t] = max(dp1[i-1][t-A[i-1]] + B[i-1], dp1[i-1][t])
            else:
                dp1[i][t] = dp1[i-1][t]
    for i in range(N, 0, -1):
        for t in range(T):
            if A[i-1] <= t:
                dp2[i][t] = max(dp2[i+1][t-A[i-1]] + B[i-1], dp2[i+1][t])
            else:
                dp2[i][t] = dp2[i-1][t]
    v = 0
    for i in range(1, N+1, 1):
        for j in range(T):
            v = max(v, dp1[i-1][j] + dp2[i+1][(T-1) - j] + B[i-1])
    return v


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, T = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: x[1])
    dp = [-1 for i in range(T*2 + 1)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T*2 + 1, 0, -1):
            if i >= a:
                if dp[i-a] >= 0:
                    dp[i] = max(dp[i], dp[i-a] + b)
    for i in range(1, T*2+1):
        dp[i] = max(dp[i], dp[i-1])
    ans = dp[-1]

    # print(dp)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, T = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: x[1])
    dp = [-1 for i in range(T*2 + 1)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T*2 + 1, 0, -1):
            if i >= a:
                if dp[i-a] >= 0 and i - a < T:
                    dp[i] = max(dp[i], dp[i-a] + b)
    for i in range(1, T*2+1):
        dp[i] = max(dp[i], dp[i-1])
    ans = dp[-1]

    # print(dp)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, T = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: x[1])
    dp = [-1 for i in range(T*2 + 1)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T*2 + 1, 0, -1):
            if i - a >= 0:
                if dp[i-a] >= 0 and i - a < T:
                    dp[i] = max(dp[i], dp[i-a] + b)
    for i in range(1, T*2+1):
        dp[i] = max(dp[i], dp[i-1])
    ans = dp[-1]

    # print(dp)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, T = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: x[1])
    dp = [-1 for i in range(T*2 + 1)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T*2 + 1, 0, -1):
            if i - a >= 0 and i - a < T:
                if dp[i-a] >= 0:
                    dp[i] = max(dp[i], dp[i-a] + b)
    for i in range(1, T*2+1):
        dp[i] = max(dp[i], dp[i-1])
    ans = dp[-1]

    # print(dp)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N, T = map(int, input().split())
    ab = [list(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: x[1])
    dp = [-1 for i in range(T*2 + 1)]
    dp[0] = 0
    for a, b in ab:
        for i in range(T*2 + 1, -1, -1):
            if i - a >= 0 and i - a < T:
                if dp[i-a] >= 0:
                    dp[i] = max(dp[i], dp[i-a] + b)
    for i in range(1, T*2+1):
        dp[i] = max(dp[i], dp[i-1])
    ans = dp[-1]

    # print(dp)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N,T = MI()
	max_T = -1
	dish = []
	for i in range(N):
		A,B = MI()
		dish.append([A,B])
		max_T = max(max_T, A)

	dp=np.array([-1 for _ in range(T+max_T)])
	dp[0] = 0
	upper = 1
	for i in range(N):
		ch2 = (dp>=0)
		ch2[T:] = False
		ch = np.roll(ch2, dish[i][0])
		ch[:i+1]=False
		dp[ch] = np.maximum(dp[ch] , dp[ch2] + dish[i][1])
	print(max(dp[:-1]))
main()

Submission status: Runtime Error

Solution code:
N,T = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(N)]
AB.sort(key=lambda x: x[1])
#print(AB)

W = T + 1
def dp(AB,W):
    N = len(AB)
    DP = [[0]*W for i in range(N+1)]
    for i in range(N):
        for w in range(W):
            if w != W:
                if AB[i][0] <= w:
                    DP[i+1][w] = max(DP[i][w-AB[i][0]]+AB[i][1],DP[i][w])
                else
                    DP[i+1][W] = DP[i][w]
            else:
                DP[i+1][w] = max(DP[i][w-1]+AB[i][1],DP[i][w])
    return DP

DP1 = dp(AB,W)

ans = DP1[N][W]
print(ans)

Submission status: Runtime Error

Solution code:
#%%
n, t = map(int, input().split())
a, b = [0] * n, [0] * n
A = max(a)
for i in range(n):
    a[i], b[i] = map(int, input().split())

dp = [[[0, -1] for _ in range(t + A + 1)] for _ in range(n + 1)]

for i in range(1, n+1):
    if i == 1:
        dp[i][a[i-1]][0] = b[i-1]
        dp[i][a[i-1]][1] = a[i-1]
    for j in range(t + A + 1):
        tmpt = j - a[i-1]
        if 0 <= tmpt :
            tmpb = dp[i-1][tmpt][0] + b[i-1]
            if tmpb >= dp[i-1][j][0]:
                dp[i][j][1] = max(dp[i-1][j][1], a[i-1])
            dp[i][j][0] = max(dp[i-1][j][0], tmpb)
        else:
            dp[i][j] = dp[i-1][j]

#print(dp[n])

ans = 0
for j in range(t + A + 1):
    if j - dp[n][j][1] <= t-1:
        ans = max(ans, dp[n][j][0])
print(ans)

Submission status: Runtime Error

Solution code:
def knapsack01(i, target_w, values, weights):
    if i == -1 or target_w == 0:
        return 0
    elif weights[i] > target_w:
        return knapsack01(i-1, target_w, values, weights)
    else:
        return knapsack01(i-1, target_w-weights[i], values, weights) + values[i]


N, T = map(int, input().split(" "))
dishes = list()
for _ in range(N):
    dishes.append(list(map(int, input().split(" "))))

dishes = sorted(dishes, key=lambda x: x[1])
w_s, v_s = zip(*dishes)
print(max([knapsack01(last_meal-1, T-1, v_s, w_s) + v_s[last_meal] for last_meal in range(N)]))

Submission status: Runtime Error

Solution code:
n, t = map(int, input().split())
d0, d1 = [0] * (t+1), [0] * (t+1)
for i in range(n):
  a, b = map(int, input().split())
  for l in range(t,a-1,-1):
    d0[l] = max(d0[l], b+d0[l-a])
    d1[l] = max(d1[l], b+d1[l-a], b+d0[l-1])
  for l in range(a-1,0,-1):
    d1[l] = max(d1[l], b+d0[l-1])
print(d1[t])