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 sys

sys.setrecursionlimit(5000)
input = sys.stdin.readline

TIME = 0
VAL = 1

N, T = [int(a) for a in input().split()]
time_value = [(-1, -1)]
for i in range(1, N + 1):
    time_value.append(tuple(int(a) for a in input().split()))

# Sort the array in the increasing order of value
time_value.sort(key = lambda x:x[VAL])


# table for knapsack problem
# maximum possible time is T-1
dp_table = {}

def knapsack(n, t):
    '''
    Input: n ... the number of elements to choose from
                 n means items 1, 2, ..., n can be chosen
           t ... time limit
    Output: total value
    '''
    if n <= 0 or t <= 0:
        return 0
    elif (n, t) in dp_table:
        return dp_table[(n, t)]
    elif time_value[n][TIME] > t:
        ans = knapsack(n - 1, t)
    else:
        ans = max(knapsack(n - 1, t),
                  time_value[n][VAL] + knapsack(n - 1, t - time_value[n][TIME]))

    dp_table[(n, t)] = ans
    return ans

def all_you_can_eat(N, T):
    val_acum = time_value[N][VAL]
    t = T - 1
    max_val = val_acum + knapsack(N - 1, t)

    for n in range(N - 1, 0, -1):  # food to eat at the end
        val_acum += time_value[n][VAL] # value[N] + value[N-1] + ... + value[n]
        t -= time_value[n + 1][TIME] # T - 1 - (time[N] + time[N-1] + ... + time[n + 1])
        if t < 0: break
        tmp = val_acum + knapsack(n - 1, t)
        max_val = max(max_val, tmp)

    return max_val

print(all_you_can_eat(N, T))

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

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
N,T=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
AB.sort(key=itemgetter(0))
dp=[[0]*(T+1) for i in range(N+1)]
ans=0
for i in range(N):
  for j in range(T):
    if AB[i][0]>j:
      dp[i+1][j]=dp[i][j]
    elif dp[i][j]>dp[i][j-AB[i][0]]+AB[i][1]:
      dp[i+1][j]=dp[i][j]
    else:
      dp[i+1][j]=dp[i][j-AB[i][0]]+AB[i][1]
  j=T
  dp[i+1][j]=dp[i][j-1]+AB[i][1]
  if ans<dp[i+1][j]:
    ans=dp[i+1][j]

print(ans)

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=sorted(AB, key=lambda x:x[0])
dp=[[0]*(T+1) for i in range(N+1)]
ans=0
for i in range(N):
  for j in range(T):
    if AB[i][0]>j:
      dp[i+1][j]=dp[i][j]
    elif dp[i][j]>dp[i][j-AB[i][0]]+AB[i][1]:
      dp[i+1][j]=dp[i][j]
    else:
      dp[i+1][j]=dp[i][j-AB[i][0]]+AB[i][1]
  j=T
  dp[i+1][j]=dp[i][j-1]+AB[i][1]
  if ans<dp[i+1][j]:
    ans=dp[i+1][j]

print(ans)

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=sorted(AB, key=lambda x:x[0])
dp=[[0]*(T+1) for i 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]
    elif dp[i][j]>dp[i][j-AB[i][0]]+AB[i][1]:
      dp[i+1][j]=dp[i][j]
    else:
      dp[i+1][j]=dp[i][j-AB[i][0]]+AB[i][1]
  j=T
  dp[i+1][j]=dp[i][j-1]+AB[i][1]

ans=0
for i in range(N+1):
  if ans<dp[i][T]:
    ans=dp[i][T]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
a = [[0 for i in range(2)] for j in range(n)]
for i in range(n):
  x, y = map(int, input().split())
  a[i][0], a[i][1] = x, y
a = sorted(a, key=lambda x: x[0], reverse=True)
dp = [[0 for i in range(t+1)] for j in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
a = []
for i in range(n):
  x, y = map(int, input().split())
  a.append([x, y])
a = sorted(a, key=lambda x: x[0], reverse=True)
dp = [[0 for i in range(t+1)] for j in range(n+1)]
for i in range(1, n+1):
  for j in range(1, t+1):
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    if j == 1:
      dp[i][j] = max(dp[i][j], a[i-1][1])
    if j >= a[i-1][0]:
      dp[i][j] = max(dp[i][j], dp[i-1][j-a[i-1][0]] + a[i-1][1])
print(dp[n][t])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(5000)
input=sys.stdin.readline

N, T = [int(a) for a in input().split()]
time = np.full(N + 1, -1, dtype = np.int32)
value = np.full(N + 1, -1, dtype = np.int32)
for i in range(1, N + 1):
    time[i], value[i] = [int(a) for a in input().split()]

# Sort the array in the increasing order of value
time = time[np.argsort(value)]
value.sort()

# table for knapsack problem
# maximum possible time is T-1
dp_table = {}

def knapsack(n, t):
    '''
    Input: n ... the number of elements to choose from
                 n means items 1, 2, ..., n can be chosen
           t ... time limit
    Output: total value
    '''
    if n <= 0 or t <= 0:
        return 0
    elif (n, t) in dp_table:
        return dp_table[(n, t)]
    elif time[n] > t:
        ans = knapsack(n-1, t)
    else:
        ans = max(knapsack(n-1, t), value[n] + knapsack(n-1, t - time[n]))

    dp_table[(n, t)] = ans
    return ans

def all_you_can_eat(n, t):
    if n <= 0 or t <= 0:
        return 0
    else:
        # Eat the most delicious food at the beginning
        tmp1 = value[n] + all_you_can_eat(n - 1, t - time[n])
        # Eat the most delicious food at the end
        tmp2 = value[n] + knapsack(n - 1, t - 1)
        return max(tmp1, tmp2)

print(all_you_can_eat(N, T))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(5000)
input=sys.stdin.readline

N, T = [int(a) for a in input().split()]
time = np.full(N + 1, -1, dtype = np.int32)
value = np.full(N + 1, -1, dtype = np.int32)
for i in range(1, N + 1):
    time[i], value[i] = [int(a) for a in input().split()]

# Sort the array in the increasing order of value
time = time[np.argsort(value)]
value.sort()

# table for knapsack problem
# maximum possible time is T-1
dp_table = np.full((N + 1, T + 1), -1, dtype = np.int32)

# Fill in dp_table
def knapsack():

    for t in range(0, T):
        dp_table[0, t] = 0

    for n in range(1, N + 1):
        dp_table[n, 0] = 0
        for t in range(1, T):
            if time[n] > t:
                dp_table[n, t] = dp_table[n - 1, t]
            else:
                dp_table[n, t] = max(dp_table[n - 1, t], value[n] + dp_table[n - 1, t - time[n]])

    return None


def all_you_can_eat(n, t):
    if n <= 0 or t <= 0:
        return 0
    else:
        # Eat the most delicious food at the beginning
        tmp1 = value[n] + all_you_can_eat(n - 1, t - time[n])
        # Eat the most delicious food at the end
        tmp2 = value[n] + dp_table[n - 1, t - 1]
        return max(tmp1, tmp2)

knapsack()
print(all_you_can_eat(N, T))

Submission status: Time Limit Exceeded

Solution code:
N,T=map(int,input().split());AB=[list(map(int,input().split())) for _ in range(N)]
dp=[0]*T
AB.sort()
m=0
for a,b in AB:
  m=max(m,dp[-1]+b)
  for j in range(T-1,a-1,-1):
    dp[j] = max(dp[j],dp[j-a]+b)

print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(5000)
input=sys.stdin.readline

N, T = [int(a) for a in input().split()]
time = np.full(N + 1, -1, dtype = np.int32)
value = np.full(N + 1, -1, dtype = np.int32)
for i in range(1, N + 1):
    time[i], value[i] = [int(a) for a in input().split()]

# Sort the array in the increasing order of value
time = time[np.argsort(value)]
value.sort()

# table for knapsack problem
# maximum possible time is T-1
dp_table = np.full((N + 1, T + 1), -1, dtype = np.int32)

def knapsack(n, t):
    '''
    Input: n ... the number of elements to choose from
                 n means items 1, 2, ..., n can be chosen
           t ... time limit
    Output: total value
    '''
    if n <= 0 or t <= 0:
        return 0
    elif dp_table[n, t] >= 0:
        return dp_table[n, t]
    elif time[n] > t:
        ans = knapsack(n-1, t)
    else:
        ans = max(knapsack(n-1, t), value[n] + knapsack(n-1, t - time[n]))

    dp_table[n, t] = ans
    return ans

def all_you_can_eat(n, t):
    if n <= 0 or t <= 0:
        return 0
    else:
        # Eat the most delicious food at the beginning
        tmp1 = value[n] + all_you_can_eat(n - 1, t - time[n])
        # Eat the most delicious food at the end
        tmp2 = value[n] + knapsack(n - 1, t - 1)
        return max(tmp1, tmp2)

print(all_you_can_eat(N, T))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = sorted(zip(A, B))

deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, 0, - 1):
    deli[i] = max(deli[i + 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    a, b = ls[i]
    for j in range(T - 1, a - 1, - 1):
        dp[j] = max(dp[j], dp[j - a] + b)
    if res < dp[- 1] + deli[i + 1]:
        res = dp[- 1] + deli[i + 1]
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = sorted(zip(A, B))
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, 0, - 1):
    deli[i] = max(deli[i + 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    a, b = ls[i]
    for j in range(T - 1, a - 1, - 1):
        dp[j] = max(dp[j], dp[j - a] + b)
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, T = map(int, input().split())
A = np.zeros([N],dtype=np.int32)
B = np.zeros([N],dtype=np.int32)
for i in range(N):
    A[i],B[i] = map(int, input().split())

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

def rec_dp(i, w, n):
    global N, DP, A2, B2
    if DP[i][w] != -1 :
        return DP[i][w]
    if i==n:
        res = 0
    elif w < A2[i]:
        res = rec_dp(i+1, w, n)
    else:
        res = max(rec_dp(i+1, w-A2[i],n)+B2[i], rec_dp(i+1, w, n))
    
    DP[i][w] = res
    return res
    
ans2 = 0
for j in range(1,N):
    DP = np.full([j+1,T],-1)
    A2 = A[0:j]
    B2 = B[0:j]
    ans = rec_dp(0,T-1,j) + B[j]
    if ans2 < ans:
        ans2 = ans

print(int(ans2))

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = sorted(zip(A, B))
#ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
#ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, 0, - 1):
    deli[i] = max(deli[i + 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, ls[i][0] - 1, - 1):
        dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N,T = map(int,readline().split())
m = map(int,read().split())
ls = sorted(zip(m,m))

deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, 0, - 1):
    deli[i] = max(deli[i + 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = sorted(zip(A, B))
#ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
#ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, 0, - 1):
    deli[i] = max(deli[i + 1], ls[i][- 1])

res = 0
dp = np.zeros(T, np.int64)
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = sorted(zip(A, B))
#ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
#ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, 0, - 1):
    deli[i] = max(deli[i + 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = sorted(zip(A, B))
#ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
#ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, - 1, - 1):
    deli[i] = max(deli[i - 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
# deli = [0]*N
# deli[- 1] = ls[-1][- 1]
deli = [ls[- 1][- 1]]
for i in range(N - 2, - 1, - 1):
    #deli[i] = max(deli[i - 1], ls[i][- 1])
    deli.append(max(deli[- 1], ls[i][- 1]))
    
deli = deli[::- 1]

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, T = map(int, readline().split())

AB= list(map(int, read().split()))
A = AB[0::2]
B = AB[1::2]
ls = list(zip(A, B))
# 食べるのにかかる時間で昇順にソート
ls.sort()
# 上の並び順において、ls[i:]の美味しさの最大値をdeli[i]とする
deli = [0]*N
deli[- 1] = ls[-1][- 1]
for i in range(N - 2, - 1, - 1):
    deli[i] = max(deli[i - 1], ls[i][- 1])

res = 0
dp = [0]*T
for i in range(N - 1):
    for j in range(T - 1, - 1, - 1):
        if ls[i][0] <= j:
            dp[j] = max(dp[j], dp[j - ls[i][0]] + ls[i][1])
    res = max(res, dp[- 1] + deli[i + 1])
print(res)

Submission status: Time Limit Exceeded

Solution code:
def all_you_can_eat(n, t, a, b):
    dp = [[0 for _ in range(2)] for _ in range(t)]
    for x in range(n):
        for i in reversed(range(t)):
            if i + a[x] < t:
                dp[i + a[x]][0] = max(dp[i + a[x]][0], dp[i][0] + b[x])
                dp[i + a[x]][1] = max(dp[i + a[x]][1], dp[i][1] + b[x])
            dp[i][1] = max(dp[i][1], dp[i][0] + b[x])
    return dp[t-1][1]


def solve():
    n, t = map(int, input().split())
    a = [0 for _ in range(n)]
    b = [0 for _ in range(n)]
    for i in range(n):
        a[i], b[i] = map(int, input().split())

    print(all_you_can_eat(n, t, a, b))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

A = []
B = []
for _ in range(N):
    aa, bb = map(int, input().split())

    A.append(aa)
    B.append(bb)

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

for x in range(1, N + 1):
    for y in range(1, T):
        if y >= A[x - 1]:
            dp1[x][y] = max(dp1[x - 1][y], dp1[x - 1][y - A[x - 1]] + B[x - 1])
        
        else:
            dp1[x][y] = dp1[x - 1][y]

dp2 = [[0] * (T) for _ in range(N + 2)]

for x in range(N, 0, -1):
    for y in range(1,T):
        if y >= A[x - 1]:
            dp2[x][y] = max(dp2[x + 1][y], dp2[x + 1][y - A[x - 1]] + B[x - 1])

        else:
            dp2[x][y] = dp2[x + 1][y]

MAX = -1
for x in range(1, N + 1):
    for y in range(T):
        MAX = max(MAX, dp1[x - 1][y] + dp2[x + 1][T - 1 - y] + B[x - 1])

print(MAX)

Submission status: Time Limit Exceeded

Solution code:
#16:25
n,t = map(int,input().split())
wv = []
for _ in range(n):
  wv.append(list(map(int,input().split())))
wv.sort(key=lambda x:x[0])
now = [0 for _ in range(t+1)]
for i in range(n):
  w,v = wv[i]
  last = now
  now = []
  for f in range(t):
    if f >= w:
      now.append(max(last[f-w]+v,last[f]))
    else:
      now.append(last[f])
  now.append(max(last[-2]+v,last[-1]))
print(now[-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import numpy as np
N,T=map(int, input().split())
val=[list(map(int, input().split())) for i in range(N)]
#import sys
#input = sys.stdin.readline
#val = list(input()) #abc
val=np.array(val)
index=np.argsort(val[:,0])
A=val[index,0]
B=val[index,1]

temp=[[0]*N for i in range(T+1)]
for jtemp in range(N-1):
    j=jtemp+1

    for itemp in range(T):
        i=itemp
        if i>=A[0]:
            temp[i][0]=B[0]
        if i>0:
            temp[i][j]=max(temp[i][j],temp[i-1][j])
            
        temp[i][j]=max(temp[i][j],temp[i][j-1])
        if A[j]<T-i:
            temp[i+A[j]][j]=max(temp[i][j-1]+B[j],temp[i+A[j]][j])
        else:
            temp[T][j]=max(temp[i][j-1]+B[j],temp[T][j])
print(max(temp[-1][:]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import numpy as np
N,T=map(int, input().split())
val=[list(map(int, input().split())) for i in range(N)]
val=np.array(val)
index=np.argsort(val[:,0])
A=val[index,0]
B=val[index,1]

temp=[[0]*N for i in range(T+1)]
for itemp in range(T):
    i=itemp
    if i>=A[0]:
        temp[i][0]=B[0]
    for jtemp in range(N-1):
        j=jtemp+1
        if i>0:
            temp[i][j]=max(temp[i][j],temp[i-1][j])
            
        temp[i][j]=max(temp[i][j],temp[i][j-1])
        if A[j]<T-i:
            temp[i+A[j]][j]=max(temp[i][j-1]+B[j],temp[i+A[j]][j])
        else:
            temp[T][j]=max(temp[i][j-1]+B[j],temp[T][j])
print(max(temp[-1][:]))

Submission status: Time Limit Exceeded

Solution code:
def joint_sort(a,b):
  # a should be cost, b should be delicious
  a, b = zip(*sorted(zip(a,b),key = lambda x:x[0]))
  return list(a), list(b)

def dp(cost, taste, n, t):
  # table[i][t]
  if n < 0:
    return 0
  else:
    table = [[0 for j in range(t+1)] for i in range(n+1)]
    for i in range(cost[0], t+1):
      table[0][i] = taste[0]
    for i in range(1, n+1):
      for j in range(t+1):
          tmp1 = table[i-1][j]
          tmp2 = 0
          if cost[i] <= j:
              tmp2 = table[i-1][j-cost[i]] + taste[i]
          table[i][j] = max(tmp1, tmp2)
    return table
n, t = map(int, input().split())
a = []
b = []
for i in range(n):
  x, y = map(int, input().split())
  a.append(x)
  b.append(y)
a, b = joint_sort(a, b)
s = -1
table = dp(a, b, n-1, t-1)
for i in range(n):
  ns = b[i] 
  if i > 0:
    ns += table[i-1][t-1]
  if ns > s:
    s = ns
print(s)

Submission status: Time Limit Exceeded

Solution code:
def joint_sort(a,b):
  # a should be cost, b should be delicious
  a, b = zip(*sorted(zip(a,b),key = lambda x:x[0]))
  return list(a), list(b)

def dp(cost, taste, n, t):
  # table[i][t]
  if n < 0:
    return 0
  else:
    table = [[0 for j in range(t+1)] for i in range(n+1)]
    for i in range(cost[0], t+1):
      table[0][i] = taste[0]
    for i in range(1, n+1):
      for j in range(t+1):
          tmp1 = table[i-1][j]
          tmp2 = 0
          if cost[i] <= j:
              tmp2 = table[i-1][j-cost[i]] + taste[i]
          table[i][j] = max(tmp1, tmp2)
    return table[n][t]
n, t = map(int, input().split())
a = []
b = []
for i in range(n):
  x, y = map(int, input().split())
  a.append(x)
  b.append(y)
a, b = joint_sort(a, b)
s = -1
for i in range(n):
  ns = b[i] + dp(a, b, i-1, t-1)
  if ns > s:
    s = ns
print(s)

Submission status: Time Limit Exceeded

Solution code:
N, T = map(int, input().split())
ls = []
for i in range(N):
  a, b = map(int, input().split())
  ls += [(a,b)]
ls.sort(key=lambda x:x[0])

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

for i in range(N):
  a,b = ls[i]
  for j in range(T-1, a-1, -1):
    dp[i+1][j] = max(dp[i][j], dp[i][j-a]+b)

last = [0]*N
last[-1] = ls[-1][1]
for i in range(N-2, -1, -1):
  last[i] = max(last[i+1], ls[i][1])

ans = 0

for i in range(1,N+1):
  ans = max(ans, max(dp[i-1])+last[i-1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,t=map(int,input().split())
dp=[[[0,0] for i in range(t)] for j in range(n+1)]
food=[list(map(int,input().split())) for i in range(n)]
foodmax=[0]*n
food.sort(key=lambda x:x[1],reverse=True)
food.sort(key=lambda x:x[0])
foodmax[-1]=food[-1][1]
for i in range(n-1)[::-1]:
  foodmax[i]=max(foodmax[i+1],food[i][1])
foodmax+=[0]
for i in range(n):
  for j in range(t):
    if j<food[i][0]:
      dp[i+1][j]=dp[i][j]
    else:
      dp[i+1][j][0]=max(dp[i][j][0],dp[i][j-food[i][0]][0]+food[i][1])
      if dp[i][j][0]>=dp[i][j-food[i][0]][0]+food[i][1]:
        dp[i+1][j][1]=dp[i][j][1]
      else:
        dp[i+1][j][1]=i
ans=0
for i in range(n+1):
  if ans<dp[i][t-1][0]+foodmax[dp[i][t-1][1]+1]:
    ans=dp[i][t-1][0]+foodmax[dp[i][t-1][1]+1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,t=map(int,input().split())
dp=[[[0,0] for i in range(t)] for j in range(n+1)]
food=[list(map(int,input().split())) for i in range(n)]
food.sort(key=lambda x:x[1],reverse=True)
food.sort(key=lambda x:x[0])
for i in range(n):
  for j in range(t):
    if j<food[i][0]:
      dp[i+1][j]=dp[i][j]
    else:
      dp[i+1][j][0]=max(dp[i][j][0],dp[i][j-food[i][0]][0]+food[i][1])
      if dp[i][j][0]>=dp[i][j-food[i][0]][0]+food[i][1]:
        dp[i+1][j][1]=dp[i][j][1]
      else:
        dp[i+1][j][1]=i
ans=0
for i in range(n+1):
  last=0
  for j in range(dp[i][t-1][1]+1,n):
    if food[j][1]>last:last=food[j][1]
  if ans<dp[i][t-1][0]+last:
    ans=dp[i][t-1][0]+last
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numpy import*
N,T,*L=int_(open(0).read().split())
d=[0]*6010
for w,v in sorted(zip(*[iter(L)]*2)):d[w:T+w]=maximum(d[w:T+w],d[:T]+v)
print(max(d))

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq



def resolve():
    (N,T)=(int(i) for i in input().split())

    dishes=[[int(i) for i in input().split()] for _ in range(N)]
    dishes.sort()
    dpt=[[-1 for i in range(T+1)] for _ in range(N+1)]
    vflg=[[False for i in range(T+1)] for _ in range(N+1)]
    dpt[0][0]=0
    q=[]
    hq.heappush(q,(0,0))

    while q:
        
        (ind,cost)=hq.heappop(q)

        if vflg[ind][cost]:
            continue
        vflg[ind][cost]=True
        if ind==N:
            break


        aft=min(cost+dishes[ind][0],T)
        sc=dpt[ind][cost]
        if dpt[ind+1][cost]<sc:
            dpt[ind+1][cost]=sc
            hq.heappush(q,(ind+1,cost))
        if cost==T:
            continue
        if dpt[ind+1][aft]<sc+dishes[ind][1]:
            dpt[ind+1][aft]=sc+dishes[ind][1]
            hq.heappush(q,(ind+1,aft))



    print(max(dpt[-1]))


if __name__ == "__main__":

    resolve()

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
lst = []
for i in range(n):
    lsti = list(map(int, input().split()))
    lst.append(lsti)

lst.sort(key=lambda x: x[0])
a, b = [], []
for i in range(n):
    lsti = lst[i]
    a.append(lsti[0])
    b.append(lsti[1])

# DPテーブルの作成
dp = [[-1 for i in range(t)] for j in range(n+1)]
for i in range(t):
    dp[0][i] = 0

# DPテーブルの更新
for i in range(n):
    for j in range(t):
        if j >= a[i]:
            dp[i+1][j] = max(dp[i][j-a[i]]+b[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]

# 答え(最大となる合計価値)
kouho = []
for i in range(n):
    kouho.append(dp[i][t-1]+b[i])
kouho.append(dp[n][t-1])
print(max(kouho))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [[0]*(T) for i in range(N)]
ans = data[0][1]
for i in range(1, N):
    for j in range(T):
        if j >= data[i-1][0]:
            value1 = dp[i-1][j]
            value2 = dp[i-1][j-data[i-1][0]] + data[i-1][1]
            dp[i][j] = max(value1, value2)
        else:
            dp[i][j] = dp[i-1][j]
    value3 = dp[i][T-1] + data[i][1]
    ans = max(value3, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import bisect
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True



def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    n, t = LMIIS()
    ab = XLMIIS(n)

    dp1 = [[0]*t for _ in range(n)]
    for i in range(1, n):
        for j in range(1, t):
            if j < ab[i-1][0]:
                dp1[i][j] = dp1[i-1][j]
            else:
                dp1[i][j] = max(dp1[i-1][j], dp1[i-1][j-ab[i-1][0]] + ab[i-1][1])


    dp2 = [[0]*t for _ in range(n)]
    for i in range(1, n):
        for j in range(1, t):
            if j < ab[n - i][0]:
                dp2[i][j] = dp2[i-1][j]
            else:
                dp2[i][j] = max(dp2[i-1][j], dp2[i-1][j-ab[n-i][0]] + ab[n-i][1])

    ans = 0
    for i in range(n):
        for j in range(t - 1):
            ans = max(ans, dp1[i][j] + dp2[n - i - 1][t - j - 1] + ab[i][1])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

_n, _t = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(_n)]
AB.sort()


def dp(t, ablist):
    ans = 0
    table = [0] * t
    for a, b in ablist:
        ans = max(ans, max(table) + b)
        if a >= t:
            continue

        rlist = [0] * (t - a)
        for i in range(t - a):
            rlist[i] = max(table[i] + b, table[a + i])

        for i in range(a, t):
            table[i] = rlist[i - a]

    return ans


print(dp(_t, AB))

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 _ in range(t)] for _ in range(n+1)]

ans = 0
i = 0
for a, b in ab:
    ans = max(ans, max(dp[i]) + b)
    if a < t:
        dp[i+1][a] = max(dp[i][a], b)
    for j in range(1, t):
        if dp[i][j] > 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j])
            if a + j < t:
                dp[i+1][a+j] = max(dp[i][a+j], dp[i][j] + b)
    i += 1

ans = max(ans, max(dp[n]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
D = []
for i in range(N):
    t, v = map(int, input().split())
    D.append((t, v))

D.sort(key=lambda x:x[0])

DP = [[0 for j in range(M)] for i in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, M):
        if j - D[i - 1][0] >= 0:
            DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - D[i - 1][0]] + D[i - 1][1])
        else:
            DP[i][j] = DP[i - 1][j]
mv = 0
for l in range(N): #ラストオーダー
    mv = max(DP[l][M - 1] + D[l][1], mv)

print(mv)

Submission status: Time Limit Exceeded

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

N,T=map(int,input().split())
D=[tuple(map(int,input().split())) for i in range(N)]
D.sort()

DP=[0]*(T+1)
ANS=0

for i in range(N):
    a,b=D[i]

    for j in range(T,a-1,-1):
        DP[j]=max(DP[j-a]+b,DP[j])

    for j in range(i+1,N):
        ANS=max(ANS,DP[T-1]+D[j][1])

print(ANS)

Submission status: Time Limit Exceeded

Solution code:
def e_all_you_can_eat():
    N, T = [int(i) for i in input().split()]
    Dishes = sorted([[int(i) for i in input().split()] for j in range(N)])

    # dp[i][j]: i 番目までの料理を j 分以内に完食できるように選んだとき、満足度の和の最大値
    dp = [[0] * (T + 1) for _ in range(N + 1)]
    ans = 0
    dp[0][0] = 0  # 食べていないときの満足度は 0 とする
    for i in range(1, N + 1):
        for j in range(T):
            dp[i][j] = dp[i - 1][j]  # i 番目を食べなかった場合

            # i 番目を食べることにした場合
            # (最後の料理は、ラストオーダー時刻が来ていなければ
            # 頼んで食いっぱなしにしてよいので、下の条件分岐と独立に考えてよい)
            ans = max(ans, dp[i][j] + Dishes[i - 1][1])

            # i 番目の料理を食べて j 分になることが可能なとき
            # (この条件を満たさないなら、i 番目の料理を食うと j 分以内に収まらない)
            if j - Dishes[i - 1][0] >= 0:
                dp[i][j] = max(dp[i][j],
                               dp[i - 1][j - Dishes[i - 1][0]] + Dishes[i - 1][1])
    return ans

print(e_all_you_can_eat())