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: Time Limit Exceeded

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]
        for i in range(t-1, -1, -1):
            if i < a:
                dp[i] = max(b, dp[i])
            else:
                dp[i] = max(dp[i-a]+b, dp[i])
    print(dp[t-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n,t=map(int, input().split())
    dp=[0]*t
    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]
        for i in range(t-1,-1,-1):
            if i < a: 
                dp[i]=max(b,dp[i])
            else:
                dp[i]=max(dp[i-a]+b,dp[i])
    print(dp[t-1])
 
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n,t=map(int, input().split())
    dp=[0]*t
    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=[0]*t
        for i in range(t):
            if i < a: 
                dptmp[i]=max(b,dp[i])
            else:
                dptmp[i]=max(dp[i-a]+b,dp[i])
        dp=dptmp
    print(dp[t-1])
 
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, t = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(n)]
    AB.sort()

    res = 0
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        a, b = AB[i - 1]
        for j in range(1, t + 1):
            if j - a >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + b)
            else:
                dp[i][j] = dp[i - 1][j]
        for k in range(i, n):
            _, b = AB[k]
            res = max(res, dp[i][j - 1] + b)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int, input().split())
A = [0]*N
B = [0]*N
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[0])
dp = [[0]*(T) for _ in range(N+1)]
ans = 0
for i in range(N):
    for j in range(T):
        dp[i+1][j] = dp[i][j]
        ans = max(ans, dp[i][j] + AB[i][1])
        if j - AB[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j], dp[i][j-AB[i][0]] + AB[i][1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
X.sort()
dp = [-1 for _ in range(T+X[-1][0]+10)]
dp[0] = 0
for i in range(N):
  for j in range(T, 0, -1):
    if dp[j-1] != -1:
      dp[j-1+X[i][0]] = max(dp[j-1+X[i][0]], dp[j-1] + X[i][1])
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 01ナップサック問題
N,W = map(int,readline().split())
AB = [tuple(map(int,readline().split())) for i in range(N)]
AB.sort(key=lambda x: x[0])
dp = [0]*(W+1)

for (w,v) in AB:
    dpnew = dp[::]
    for j in range(W):
        dpnew[min(j+w,W)] = max(dp[min(j+w,W)],dp[j] + v)
    dp = dpnew

print(dp[W])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 01ナップサック問題
N,W = map(int,readline().split())
AB = [tuple(map(int,readline().split())) for i in range(N)]
AB.sort(key=lambda x: x[0])
dp = [0]*(W+1)

for (w,v) in AB:
    dpnew = dp[::]
    for j in range(W):
        dpnew[min(j+w,W)] = max(dp[min(j+w,W)],dp[j] + v)
    dp = dpnew

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,t = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
ab.sort() # 食べるのが早い順にソート

# ナップザック問題に落とし込む
dp = [[0 for i in range(t+1)]for j in range(n+1)]

for i in range(n):
    ti,vi = ab[i]
    for j in range(t+1):
        # 食べたほうがよい(t秒以内かつ満足度が上がるならば)
        if j + ti <= t:
            dp[i+1][j+ti] = max(dp[i+1][j+ti],dp[i][j]+vi)
        # 食べなかった場合の最高値を更新
        dp[i+1][j] = max(dp[i][j],dp[i+1][j])

ma = 0

for i in range(n):
    # 最後にi番目の皿を食べることができる
    ma = max(ma,dp[i][t-1]+ab[i][1])

print(ma)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, t = map(int, input().split())
    AB = sorted([list(map(int, input().split())) for _ in range(n)], key=lambda x: x[0])

    res = 0
    dp = [[0] * (t + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        a, b = AB[i - 1]
        for j in range(1, t + 1):
            if j - a >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a] + b)
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])
        now = dp[i - 1][t - 1] + b
        res = max(res, now)

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

n, t = map(int, input().split())
m = map(int, read().split())
AB = sorted(zip(m, m))
A, B = zip(*AB)
dp = [[0]*t for _ in range(n+1)]
for i, a in enumerate(A[:-1]):
  for j in range(t):
    if j < a:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-a]+B[i], dp[i][j])
ans = 0
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
for i in range(n-1):
  ans = max(ans, dp[i+1][-1] + maxB[i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    n, t = map(int, input().split())
    foods = []
    limit = 0
    tt = []
    for i in range(n):
        a, b = map(int, input().split())
        foods.append((a,b))
        limit += a
        tt.append(a)
    c = max(tt) * 2
    foods.sort(key=lambda x:(x[0], -x[1]))
    limit = min(limit * 2, t * 2)
    time = [0 for _ in range(limit+c)]
    used = [0] * (limit + c)
    used[0] = 1

    for a,b in foods:
        for i in range(limit+c)[::-1]:
            if used[i] and i+a*2 < limit + c and time[i+a*2] < time[i] + b:
                time[i+a*2] = time[i] + b
                if i+a*2 < limit:
                    used[i+a*2] = 1

    print(max(time))

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,t=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
dp1=np.zeros((n+1,t),int)
dp2=np.zeros((n+2,t),int)
# dp1[i][j]:0<=i<=n:i個目までの料理で考えたとき（i個の料理）、時間j以内で食べられるおいしさの総和
# dp2[i][j]:1<=i<=n+1:i個目以降の料理で考えたとき（n-i+1個の料理）、時間j以内で食べられるおいしさの総和
for i in range(n):
  a,b=ab[i]
  dp1[i+1,:a]=dp1[i,:a]
  dp1[i+1,a:]=np.maximum(dp1[i,a:],dp1[i,:-a]+b)
  j=n-i
  a,b=ab[j-1]
  dp2[j,:a]=dp2[j+1,:a]
  dp2[j,a:]=np.maximum(dp2[j+1,a:],dp2[j+1,:-a]+b)
ans=0
for i in range(1,n+1):# i個目の料理を最後に食べるとするとき。
  ai=max([dp1[i-1][j]+dp2[i+1][t-1-j] for j in range(t)])
  ans=max(ans,ai+ab[i-1][1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,t=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n)]
import numpy as np
def func(j):
  dp=np.zeros(3001,np.int64)
  # dp[i]:時間合計i以内に食べれる料理のおいしさ総和
  for i in range(n):
    if j==i:
      continue
    a,b=ab[i]
    dp[a:]=np.maximum(dp[a:],dp[:-a]+b)
  return dp[t-1]
ans=0
for i in range(n):
  ans=max(ans,func(i)+ab[i][1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,T,*ab = map(int, read().split())

    AB = []
    for a, b in zip(*[iter(ab)]*2):
        AB.append((a, b))

    AB.sort()
    
    dp = [[0] * (T+1) for _ in range(N+1)]

    ans = 0
    for i in range(N):
        w_i, v_i = AB[i]
        for j in range(T):
            if j < w_i:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j - w_i] + v_i, dp[i][j])
        
        ans = max(ans, dp[i][T-1] + v_i)
    
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    dp = [-1] * (T + 3000)
    dp[0] = 0
    for a, b in sorted(AB):
        for i in range(T - 1, -1, -1):
            if dp[i] == -1:
                continue
            dp[i + a] = max(dp[i + a], dp[i] + b)
    print(max(dp))


main()

Submission status: Time Limit Exceeded

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

dp = [-1] * (T + 3000)
dp[0] = 0
for a, b in sorted(AB):
    for i in range(T - 1, -1, -1):
        if dp[i] == -1:
            continue
        if dp[i + a] < dp[i] + b:
            dp[i + a] = dp[i] + b
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
#ALL you can eat 
#0-1 なっぷサック問題をとく* N

#要領T-1のバックと　大きさがA,価値がBの荷物がNこずつある。　この時これらを使って価値をT-1をこえない範囲で最大にする方法を考える。


#dpl[N][V]=1番目からN番目までの荷物を用いて、重さをVにする上で実現可能な価値の最大値
N,T=map(int,input().split())
d=[]
for i in range(N):
    a,b=map(int,input().split())
    d.append((a,b))
dpl=[[0 for i in range(T)] for j in range(N+1)]
for i in range(N):
    weight,value=d[i]
    for j in range(T):
        if j>=weight:
            dpl[i+1][j]=max(dpl[i][j],dpl[i][j-weight]+value)
        else:
            dpl[i+1][j]=dpl[i][j]

            
#dpr[K][V]=K番目からN番目までの荷物を用いて、重さをVにする上で実現可能な価値の最大値
dpr=[[0 for i in range(T)] for j in range(N+2)]
for i in range(1,N+1):
    weight,value=d[-i]
    for j in range(T):
        if j>=weight:
            dpr[N+1-i][j]=max(dpr[N+2-i][j],dpr[N+2-i][j-weight]+value)
        else:
            dpr[N+1-i][j]=dpr[N+2-i][j]

#dpr[K][V]=K番目からN番目までの荷物を用いて重さをV以下にする上で実現可能な価値の最大値にする
for i in range(1,N+1):
    for j in range(1,T):
        dpr[i][j]=max(dpr[i][j],dpr[i][j-1])
    
ans=0
for i in range(N):
    sub=d[i][1]
    #i+1番目の物を使わない
    add=0
    for j in range(T):
        add=max(add,dpl[i][j]+dpr[i+2][T-1-j])
    sub+=add
    ans=max(sub,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,T=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]
#dp[i][j] 料理iまでの間で、時間jまでに達成できる最大効用
dp=[[0]*(T+1) for _ in range(N+1)]
AB.sort()
for i in range(1,N+1):
  dp[i]=dp[i-1][:]
  time=AB[i-1][0]
  happy=AB[i-1][1]
  for j in range(T):
    dp[i][min(j+time,T)]=max(dp[i][min(j+time,T)],dp[i-1][j]+happy)
print(dp[N][T])

Submission status: Time Limit Exceeded

Solution code:
N,T=map(int,input().split())
A,B=[],[]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a);B.append(b)
dp=[[[0,0] for i in range(T)] for i in range(N+1)]

for i in range(N):
    for j in range(T):
        if j-A[i]>=0:
            dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j-A[i]][0]+B[i])
            dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j-A[i]][1]+B[i])
        dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][0])
        dp[i+1][j][1]=max([dp[i+1][j][1],dp[i][j][0]+B[i],dp[i][j][1]])
ans=max(dp[N][T-1][0],dp[N][T-1][1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
n,t = map(int,readline().split())
f = []
m = 0
for i in range(n):
  p,q = map(int,readline().split())
  m = max(m,p)
  f.append((p,q))
  
f.sort()
dp = [[0]*(t+m) for i in range(n+1)]

for i,c in enumerate(f):
  a,b = c
  for j in range(t+m):
    if j-a >= t:
      break
    if j < a :
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-a]+b)
      
print(max(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,t = map(int,input().split())
f = []
m = 0
for i in range(n):
  p,q = map(int,input().split())
  m = max(m,p)
  f.append((p,q))
  
f.sort()
dp = [[0]*(t+m) for i in range(n+1)]

for i,c in enumerate(f):
  a,b = c
  for j in range(t+m):
    if j < a or j-a >= t:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j],dp[i][j-a]+b)
      
print(max(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,t=map(int,input().split())
    ab=[list(map(int,input().split())) for _ in [0]*n]
    ab.sort(key=lambda x:x[0])
    dp=[0]*(t+1)
    for a,b in ab:
        for i in range(t-1,-1,-1):
            if a+i>=t:
                dp[t]=max(dp[t],dp[i]+b)
            else:
                dp[i+a]=max(dp[i+a],dp[i]+b)
    print(max(dp))
main()

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int, input().split())
table = [[0] * (N + 1) for _ in range(T + 1)]
dish = sorted((tuple(map(int, input().split())) for _ in range(N)), key=lambda t: t[0])
for t in range(T + 1):
    for n in range(N):
        minutes_to_take, deliciousness = dish[n]
        now = table[t][n]
        if t < T:
            table[min(T, t + minutes_to_take)][n + 1] = max(table[min(T, t + minutes_to_take)][n + 1], now + deliciousness)
        if n < N:
            table[t][n + 1] = max(table[t][n + 1], now)
print(max(table[t][N] for t in range(T + 1)))

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
a, b, ab = [], [], []
for _ in range(n):
    ab.append(tuple(map(int, input().split())))
ab.sort(key=lambda x:x[0])
for i in ab:
    a.append(i[0])
    b.append(i[1])

# dp[i][j] = 0~i番目の料理でj分以内に完食できる美味しさの合計の最大値
# 0 <= i < n-1, 0 <= j <= t-1
dp = [[0 for _ in range(min([t, a[0]]))] + [b[0] for _ in range(t-a[0])]]
for i in range(1, n-1):
    dp.append([])
    for j in range(min([t, a[i]])):
        dp[i].append(dp[i-1][j])
    for j in range(a[i], t):
        dp[i].append(max([dp[i-1][j], dp[i-1][j-a[i]]+b[i]]))

ans = []
for i in range(1, n):
    ans.append(dp[i-1][t-1] + b[i])
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
a, b, ab = [], [], []
for _ in range(n):
    ab.append(tuple(map(int, input().split())))
ab.sort(key=lambda x:x[0])
for i in ab:
    a.append(i[0])
    b.append(i[1])

# dp[i][j] = 0~i番目の料理でj分以内に完食できる美味しさの合計の最大値
# 0 <= i <= n-1, 0 <= j <= t-1
dp = [[0 for _ in range(min([t, a[0]]))] + [b[0] for _ in range(t-a[0])]]
for i in range(1, n):
    dp.append([])
    for j in range(min([t, a[i]])):
        dp[i].append(dp[i-1][j])
    for j in range(a[i], t):
        dp[i].append(max([dp[i-1][j], dp[i-1][j-a[i]]+b[i]]))

ans = []
for i in range(1, n):
    ans.append(dp[i-1][t-1] + b[i])
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
a, b, ab = [], [], []
for _ in range(n):
    ab.append(tuple(map(int, input().split())))
ab.sort(key=lambda x:x[0])
for i in ab:
    a.append(i[0])
    b.append(i[1])

# dp[i][j] = 0~i番目の料理でj分以内に完食できる美味しさの合計の最大値
# 0 <= i <= n-1, 0 <= j <= t-1
dp = [[0 for _ in range(a[0])] + [b[0] for _ in range(t-a[0])]]
for i in range(1, n):
    dp.append([])
    for j in range(min([t, a[i]])):
        dp[i].append(dp[i-1][j])
    for j in range(a[i], t):
        dp[i].append(max([dp[i-1][j], dp[i-1][j-a[i]]+b[i]]))

ans = []
for i in range(1, n):
    ans.append(dp[i-1][t-1] + b[i])
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
N , T = map(int,input().split())
AB = []
for _ in range(N):
    AB.append(list(map(int,input().split())))
dp = [-1] * (T+3000)
dp[0] = 0
for a,b in sorted(AB):
    for i in range(T-1,-1,-1):
        if dp[i] == -1:
            continue
        if dp[i+a] < dp[i] + b:
            dp[i+a] = dp[i] +b 
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
N , T = map(int,input().split(' '))
AB = []
for _ in range(N):
    AB.append(list(map(int,input().split())))
dp = [-1] * (T+3000)
dp[0] = 0
for a,b in sorted(AB):
    for i in range(T-1,-1,-1):
        if dp[i] == -1:
            continue
        if dp[i+a] < dp[i] + b:
            dp[i+a] = dp[i] +b 
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
n,t = map(int,input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
dp = [[0 for i in range(t+1)]for j in range(n+1)]
for i in range(n):
    ti,vi = ab[i]
    for j in range(t+1):
        if j + ti <= t:
            dp[i+1][j+ti] = max(dp[i+1][j+ti],dp[i][j]+vi)
        dp[i+1][j] = max(dp[i][j],dp[i+1][j])
ma = 0
for i in range(n):
    ma = max(ma,dp[i][t-1]+ab[i][1])
print(ma)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,t = map(int,input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
dp = np.array([[0 for i in range(t+1)]for j in range(n+1)])
for i in range(n):
    ti,vi = ab[i]
    for j in range(t+1):
        if j + ti <= t:
            dp[i+1][j+ti] = max(dp[i+1][j+ti],dp[i][j]+vi)
        dp[i+1][j] = max(dp[i][j],dp[i+1][j])
ma = 0
for i in range(n):
    ma = max(ma,dp[i][t-1]+ab[i][1])
print(ma)

Submission status: Time Limit Exceeded

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

dp=[0]*(T+1)

for a,b in item:
    for t in reversed(range(T)):
        dist=min(T,t+a)
        dp[dist] = max(dp[t]+b,dp[dist])
print(max(dp))

Submission status: Time Limit Exceeded

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

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

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

for i,(a,b) in  enumerate(item,1):
    for t in reversed(range(T)):
        dist=t+a
        dp[i][dist] = max(dp[i-1][t]+b,dp[i][dist])
        dp[i][t]=max(dp[i-1][t],dp[i-1][t])
ans=0
for l in dp:
    ans=max(ans,max(l))
print(ans)

Submission status: Time Limit Exceeded

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

DP = [[0] * T for _ in range(N-1)]

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

ans = 0
tmp = 0

for i in reversed(range(N-1)):
	tmp = max(tmp, AB[i+1][1])
	ans = max(ans, DP[i][T-1] + tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, T = map(int, input().split())
I = np.array(read().split(), dtype = np.int32)
A = I[::2]
B = I[1::2]

sort_ind = np.argsort(A)
A = A[sort_ind]
B = B[sort_ind]

DP = np.zeros([N-1, T], dtype = np.int32)
DP[0,A[0]:] = B[0]

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

tmp = 0
for i in reversed(range(N)):
	tmp = max(B[i], tmp)
	B[i] = tmp

C = DP[:,T-1] + B[1:]
print(np.max(C))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, T = map(int, input().split())
I = np.array(read().split(), dtype = np.int64)
A = I[::2]
B = I[1::2]

sort_ind = np.argsort(A)
A = A[sort_ind]
B = B[sort_ind]

DP = [[0] * (T) for _ in range(N-1)]
for i in range(N-1):
	for j in range(T):
		if i == 0:
			if j >= A[0]:
				DP[i][j] = B[0]
		else:
			if j >= A[i]:
				DP[i][j] = max(DP[i-1][j], DP[i-1][j-A[i]] + B[i])
			else:
				DP[i][j] = DP[i-1][j]




# DP = np.zeros([N-1, T], dtype = np.int64)
# DP[0,A[0]:] = B[0]

# for i in range(1, N-1):
# 	for j in range(T):
# 		if j - A[i] >= 0:
# 			DP[i,j] = max(DP[i-1, j], DP[i-1,j-A[i]] + B[i])
# 		else:
# 			DP[i,j] = DP[i-1,j]

tmp = 0
for i in reversed(range(N)):
	tmp = max(B[i], tmp)
	B[i] = tmp
ans = 0
for i in range(N-1):
	ans = max(ans, DP[i][T-1] + B[i+1])

print(ans)

# C = DP[:,T-1] + B[1:]
# print(np.max(C))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, T = map(int, input().split())
I = np.array(read().split(), dtype = np.int64)
A = I[::2]
B = I[1::2]

sort_ind = np.argsort(A)
A = A[sort_ind]
B = B[sort_ind]

DP = np.zeros([N-1, T], dtype = np.int64)
DP[0,A[0]:] = B[0]

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

tmp = 0
for i in reversed(range(N)):
	tmp = max(B[i], tmp)
	B[i] = tmp

C = DP[:,T-1] + B[1:]
print(np.max(C))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d={i:0 for i in range(3001)}
db={i:0 for i in range(3001)}

n,t=map(int,input().split())

x=sorted([tuple(map(int,input().split()))for i in range(n)],key=lambda xxx:xxx[0])
dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
        else:
            break
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
        else:
            break

    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d={i:0 for i in range(3001)}
db={i:0 for i in range(3001)}

n,t=map(int,input().split())

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

dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d=defaultdict(int)
db=defaultdict(int)

d[0]=0
db[0]=0

n,t=map(int,input().split())

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

dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            tmp=dp[i][j]+dp2[i][t-j-1]
            if ans<tmp:
                ans=tmp
        else:
            tmp=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
            if tmp>ans:
                ans=tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d=defaultdict(int)
db=defaultdict(int)

d[0]=0
db[0]=0

n,t=map(int,input().split())

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

dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if d[i]>l[-1]:
            l.append(d[i])
        else:
            l.append(l[-1])

    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        if db[i]>l[-1]:
            l.append(db[i])
        else:
            l.append(l[-1])
        
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            if ans<dp[i][j]+dp2[i][t-j-1]:
                ans=dp[i][j]+dp2[i][t-j-1]
        else:
            if dp[i][j]+dp2[i][t-j-1]+x[i-1][1]>ans:
                ans=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import*
import sys
input=sys.stdin.readline   #input高速化 １文字の時の改行文字に注意+

d=defaultdict(int)
db=defaultdict(int)

d[0]=0
db[0]=0

n,t=map(int,input().split())

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

dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        l.append(max(d[i],l[-1]))
    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        l.append(max(db[i],l[-1]))
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0

for i in range(len(dp)):
    for j in range(t):
        if i==0 or i==len(dp)-1:
            if ans<dp[i][j]+dp2[i][t-j-1]:
                ans=dp[i][j]+dp2[i][t-j-1]
        else:
            if dp[i][j]+dp2[i][t-j-1]+x[i-1][1]>ans:
                ans=dp[i][j]+dp2[i][t-j-1]+x[i-1][1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import*

d=defaultdict(int)
db=defaultdict(int)

d[0]=0
db[0]=0

n,t=map(int,input().split())

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

dp=[]
dp2=[]
for time,value in x:
    for k,v in d.copy().items():
        if k+time<t:
            if d[k+time]<v+value:
                d[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        l.append(max(d[i],l[-1]))
    dp.append(l)    
        
for time,value in x[::-1]:
    for k,v in db.copy().items():
        if k+time<t:
            if db[k+time]<v+value:
                db[k+time]=v+value
    l=[0]
    for i in range(1,t+1):
        l.append(max(db[i],l[-1]))
    dp2.append(l)
dp=[[0]*t,[0]*t]+dp
dp2=([[0]*t,[0]*t]+dp2)[::-1]

ans=0
#print(dp2)
for i in range(len(dp)):
    for j in range(t):
#        print(ans,i)
        if i==0 or i==len(dp)-1:
            ans=max(dp[i][j]+dp2[i][t-j-1],ans)
        else:
#            print(i,t-j-1)
            dp2[i][t-j-1]
            ans=max(dp[i][j]+dp2[i][t-j-1]+x[i-1][1],ans)
    
print(ans)

Submission status: Time Limit Exceeded

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

dp = [-1] * (T + 3000)
dp[0] = 0
c = 0
for a, b in sorted(AB):
    for j in range(c, -1, -1):
        if dp[j] == -1:
            continue
        t = dp[j] + b
        if dp[j + a] < t:
            dp[j + a] = t
    c = min(c + a, T - 1)
print(max(dp))

Submission status: Time Limit Exceeded

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

dp = [-1] * (T + 3000)
dp[0] = 0
for a, b in sorted(AB):
    for j in range(T - 1, -1, -1):
        if dp[j] == -1:
            continue
        t = dp[j] + b
        if dp[j + a] < t:
            dp[j + a] = t
print(max(dp))