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:
N, T = map(int, input().split())
data = []
for i in range(N):
  a, b = map(int, input().split())
  data.append((a,b))
data.sort()

#print(data)

dp = [0] * T
ans = 0
for a, b in data:
  ans = max(ans, dp[-1]+b)
  if a < T:
    eatable = dp[:T-a]
    j = 0
    for i in range(a, T, 1):
      if dp[i] < eatable[j] + b:
        dp[i] = eatable[j] + b
      j += 1
print(ans)

Submission status: Time Limit Exceeded

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

#print(data)

dp = [0] * T
ans = 0
for a, b in data:
  ans = max(ans, dp[-1]+b)
  if a < T:
    eatable = dp[:T-a]
    j = 0
    maxj = len(eatable)
    for i in range(a, T, 1):
      if dp[i] < eatable[j] + b:
        dp[i] = eatable[j] + b
      if not j==maxj:
        j += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, t = map(int, input().split())
dish = [list(map(int, input().split())) for _ in range(n)]
dish.sort(key=lambda x: x[0])
dp = [[0 for _ in range(3000)] for _ in range(3000)]
ans = 0

for i in range(n):
    for j in range(t):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        nj = j + dish[i][0]
        if nj < t:
            dp[i + 1][nj] = max(dp[i + 1][nj], dp[i][j] + dish[i][1])
    now = dp[i][t- 1] + dish[i][1]
    ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

d.sort(key=lambda x: x[1])

for n in range(N):
    d1 = d[n]
    d2 = d[0:n]+d[n+1:]

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

    # dp[N-1][T-1]
    for i in range(N-1):
        if i == 0:
            for j in range(d2[0][0], T):
                dp[0][j] = d2[0][1]
            continue

        for j in range(T):

            if j-d2[i][0] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-d2[i][0]] + d2[i][1])

    ans = max(ans, dp[N-2][T-1] + d1[1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,w = map(int,input().split())
items = sorted([list(map(int,input().split())) for i in range(n)])
dp = [[0]*(w+1) for _ in range(n+2)]
for i in range(n):
    wi, vi = items[i]
    for j in range(w+1):
        if j+wi<=w:
            dp[i+1][j+wi] = max(dp[i+1][j+wi], dp[i][j]+vi)
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
ans = 0
for i, (wi, vi) in enumerate(items):
    ans = max(ans, dp[i][w-1]+vi)
print(ans)

Submission status: Time Limit Exceeded

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

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

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

a, b = AB[0]
if a < T:
  DP[0][a][0] = b
DP[0][0][1] = b

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

ans = 0
for i in range(T):
  ans = max(ans, DP[-1][i][0])
  ans = max(ans, DP[-1][i][1])

print(ans)

Submission status: Time Limit Exceeded

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

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

a, b = AB[0]
if a < T:
  DP[0][a][0] = b
DP[0][0][1] = b

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

ans = 0
for i in range(T):
  ans = max(ans, DP[-1][i][0])
  ans = max(ans, DP[-1][i][1])

print(ans)

Submission status: Time Limit Exceeded

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

AB.sort()

# dp[i][j]: 満足度の最大値
# i: i品目まで
# j: 制限時間(< T)
dp = [[0] * 3100 for _ in range(3100)]

dp[0][0] = 0

# 貰うDP
ans = 0
for i in range(1, N + 1):
    for j in range(T):
        dp[i][j] = dp[i - 1][j]
        
        # ラストオーダーはAB[i - 1]
        ans = max(ans, dp[i][j] + AB[i - 1][1])

        if j - AB[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - AB[i - 1][0]] + AB[i - 1][1])

print(ans)

Submission status: Time Limit Exceeded

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

AB.sort(key=lambda x: (x[0],x[1]))

# dp[i][j]: 満足度の最大値
# i: i品目まで
# j: 制限時間(< T)
dp = [[0] * 3100 for _ in range(3100)]

dp[0][0] = 0

# 貰うDP
ans = 0
for i in range(1, N + 1):
    for j in range(T):
        dp[i][j] = dp[i - 1][j]
        
        # ラストオーダーはAB[i - 1]
        ans = max(ans, dp[i][j] + AB[i - 1][1])

        if j - AB[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - AB[i - 1][0]] + AB[i - 1][1])

print(ans)

Submission status: Time Limit Exceeded

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)]
wv.sort(key = lambda x:x[1],reverse = True)
res = 0
for i in range(min(n,10)):
    dp = [[0] * (t+5) for _ in range(n+5)]
    for j in range(n):
        w,v = wv[j]
        for k in range(t):
            if k < w or i == j:
                dp[j+1][k] = dp[j][k]
            else:
                dp[j+1][k] = max(dp[j][k], dp[j][k-w] + v)
    # print(dp[n][t-1])
    res = max(dp[n][t-1] + wv[i][1], res)
print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import namedtuple
    from operator import attrgetter

    Dish = namedtuple('Dish', 'time deliciousness')

    N, T = map(int, input().split())
    dishes = []
    for _ in range(N):
        a, b = map(int, input().split())
        d = Dish(time=a, deliciousness=b)
        dishes.append(d)

    dishes.sort(key=attrgetter('time'))

    dp = [0] * T
    ma = 0
    ret = 0
    for d in dishes:
        ret = max(ret, ma + d.deliciousness)
        for t in range(T - 1, d.time - 1, -1):
            dp[t] = max(dp[t], dp[t - d.time] + d.deliciousness)
            ma = max(ma, dp[t])
    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Time Limit Exceeded

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

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

    AB.sort(key=lambda x: x[0])
    maxA = 0
    for a, b in AB:
        maxA = max(maxA, a)

    dp = [-1]*(T+maxA)
    dp[0] = 0

    for a, b in AB:
        for i in range(T+maxA-1, -1, -1):
            if i >= T:
                if i-a < T and i-a >= 0 and dp[i-a] >= 0:
                    dp[i] = max(dp[i], dp[i-a] + b)

            elif i - a >= 0 and dp[i-a] >= 0:
                dp[i] = max(dp[i], dp[i-a] + b)

    print(max(dp))
main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

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 SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    n,t=MI()
    ab=LLI(n)
    ab.sort()
    dp=[-1]*(t+1)
    dp[0]=0
    for a,b in ab:
        for i in range(t-1,-1,-1):
            pre=dp[i]
            if pre==-1:continue
            ni=min(t,i+a)
            dp[ni]=max(dp[ni],pre+b)
    print(max(dp))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, T = lr()
AB = [lr() for _ in range(N)]
AB.sort()
# 1つ除いたDP, DP[T-1]に除いたおいしさを足す
answer = 0
for i in range(N):
    dp = np.zeros(T, np.int64)
    for j in range(N):
        if j == i:
            continue
        sweet = AB[j][1]
        time = AB[j][0]
        dp[time:] = np.maximum(dp[time:], dp[:-time] + sweet)
    answer = max(answer, dp[-1] + AB[i][1])

print(answer)

Submission status: Time Limit Exceeded

Solution code:
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 = dp = [[0 for _ in range(3005)] for _ in range(3005)]
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] + b
    ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

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

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][0] >= 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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

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

Solution code:
from math import floor
from math import sqrt
from collections import deque
import numpy
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

# https://atcoder.jp/contests/abc145/tasks/abc145_e
# E - All-you-can-eat
"""
"""

N = gi()
T = gi()
A = [0] * (N + 5)
B = [0] * (N + 5)
for i in range(1, N + 1):
    A[i] = gi()
    B[i] = gi()

pref = [[0 for x in range(T + 5)] for i in range(N + 5)
       ]  #pop i order is inversed
suff = [[0 for x in range(T + 5)] for i in range(N + 5)]


def precalc():
    for i in range(1, N + 1):
        for t in range(T):  # max T - 1 complete minutes
            pref[i][t] = max(pref[i][t], pref[i - 1][t])
            if t >= A[i]:
                pref[i][t] = max(pref[i][t], pref[i - 1][t - A[i]] + B[i])

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


precalc()

ans = 0

for li in range(1, N + 1):
    for pt in range(T):
        ans = max(ans, pref[li - 1][pt] + suff[li + 1][T - 1 - pt] + B[li])
print(ans)

Submission status: Time Limit Exceeded

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
from bisect import bisect, bisect_left, bisect_right

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()
A = []
B = []
L = [LIST() for i in range(N)]

# 1からi番目の料理で，j分以内に完食できるおいしさの合計の最大値
# dp1[i][j]
dp1 = [[0] * (T) for i in range(N+1)]
# # iからN番目の料理で，j分以内に完食できるおいしさの合計の最大値
# # dp2[i][j]
# dp2 = [[0] * (T) for i in range(N+1)]
# print(L)
# 昇順にする
L.sort()
for a, b in L:
    A.append(a)
    B.append(b)

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

ans = 0
# 最後に一番時間のかかるものをT-1秒目に食べればいい
for k in range(1, N+1):
    ans = max(dp1[k-1][T-1] + B[k-1], ans)
print(ans)




exit()
for i in range(N):
    for j in range(T):
        if j - A[i] >= 0:
            dp1[i+1][j] = max(dp1[i][j-A[i]] + B[i], dp1[i+1][j])
        dp1[i+1][j] = max(dp1[i][j], dp1[i+1][j])
# やりやすく
L = L[::-1]
for i in range(N):
    for j in range(T):
        if j - A[i] >= 0:
            dp2[i+1][j] = max(dp2[i][j-A[i]] + B[i], dp2[i+1][j])
        dp2[i+1][j] = max(dp2[i][j], dp2[i+1][j])
# 戻す
L = L[::-1]
print(L)
ans = 0
for i in range(1, N+1):
    tmp = 0
    for j in range(T):
        tmp = max(tmp, dp1[i-1][j] + dp1[N-i][T-1-j])
    ans = max(ans, tmp+L[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)]

ab.sort()

dp = [0] * t

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

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()

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, T = map(int, input().split())
    ab = [tuple(map(int, input().split())) for i in range(N)]
    ab.sort(key=lambda x: x[0])
    t = ab[-1][0]
    dp = [-1]*(T+t+1)
    dp[0] = 0
    for a, b in ab:
        for i in range(T-1, -1, -1):
            if dp[i] < 0:
                continue
            dp[i+a] = max(dp[i+a], dp[i]+b)
    ans = max(dp)
    print(ans)


main()

Submission status: Time Limit Exceeded

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


main()

Submission status: Time Limit Exceeded

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


main()

Submission status: Time Limit Exceeded

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


main()

Submission status: Time Limit Exceeded

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

    # print(dp)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def solve_145e():
    from collections import namedtuple
    from operator import attrgetter
    import sys
    input = sys.stdin.readline

    Food = namedtuple('Food', 'time_to_eat deliciousness')

    N, T = map(int, input().split())
    foods = []
    for _ in range(N):
        row = map(int, input().split())
        foods.append(Food(*row))
    foods.sort(key=attrgetter('time_to_eat'))
    # 同じ料理の組を食べるなら時間のかかるものを後回しにしても結果は悪くならない

    dp = [-1] * T
    dp[0] = 0
    # dp[time]:=timeに食べ終わる注文の仕方で得られる最大満足度

    ma = 0  # 回答候補
    ca = 0  # フィニッシュ前候補
    for food in foods:
        # これでフィニッシュの場合
        ma = max(ma, ca + food.deliciousness)

        # まだ食べる場合
        for time in range(T - 1 - food.time_to_eat, -1, -1):
            if ~dp[time]:
                when_eat = dp[time] + food.deliciousness
                if dp[time + food.time_to_eat] < when_eat:
                    dp[time + food.time_to_eat] = when_eat
                    ca = max(ca, when_eat)

    print(ma)
    return


if __name__ == '__main__':
    solve_145e()

Submission status: Time Limit Exceeded

Solution code:
def solve_145e():
    from collections import namedtuple
    from operator import attrgetter
    import sys
    input = sys.stdin.readline

    Food = namedtuple('Food', 'time_to_eat deliciousness')

    N, T = map(int, input().split())
    foods = []
    for _ in range(N):
        row = map(int, input().split())
        foods.append(Food(*row))
    foods.sort(key=attrgetter('time_to_eat'))
    # 同じ料理の組を食べるなら時間のかかるものを後回しにしても結果は悪くならない

    dp = [-1] * T
    dp[0] = 0
    # dp[time]:=timeに食べ終わる注文の仕方で得られる最大満足度

    ma = 0  # 回答候補
    ca = 0  # フィニッシュ前候補
    for food in foods:
        # これでフィニッシュの場合
        ma = max(ma, ca + food.deliciousness)

        # まだ食べる場合
        for time in reversed(range(T - food.time_to_eat)):
            if ~dp[time]:
                when_eat = dp[time] + food.deliciousness
                if dp[time + food.time_to_eat] < when_eat:
                    dp[time + food.time_to_eat] = when_eat
                    ca = max(ca, when_eat)

    print(ma)
    return


if __name__ == '__main__':
    solve_145e()

Submission status: Time Limit Exceeded

Solution code:
def solve_145e():
    from collections import namedtuple
    from operator import attrgetter
    import sys
    input = sys.stdin.readline

    Food = namedtuple('Food', 'time_to_eat deliciousness')
    INF = 3000 * 3000 + 1

    N, T = map(int, input().split())
    foods = []
    for _ in range(N):
        row = map(int, input().split())
        foods.append(Food(*row))
    foods.sort(key=attrgetter('time_to_eat'))
    # 同じ料理の組を食べるなら時間のかかるものを後回しにしても結果は悪くならない

    dp = [-INF] * T
    dp[0] = 0
    # dp[time]:=timeに食べ終わる注文の仕方で得られる最大満足度

    ma = 0  # 回答候補
    ca = 0  # フィニッシュ前候補
    for food in foods:
        # これでフィニッシュの場合
        ma = max(ma, ca + food.deliciousness)

        # まだ食べる場合
        for time in reversed(range(T - food.time_to_eat)):
            when_eat = dp[time] + food.deliciousness
            if dp[time + food.time_to_eat] < when_eat:
                dp[time + food.time_to_eat] = when_eat
                ca = max(ca, when_eat)

    print(ma)
    return


if __name__ == '__main__':
    solve_145e()

Submission status: Time Limit Exceeded

Solution code:
def solve_145e():
    from collections import namedtuple
    from operator import attrgetter
    import sys
    input = sys.stdin.readline

    Food = namedtuple('Food', 'time_to_eat deliciousness')
    INF = 3000 * 3000 + 1

    N, T = map(int, input().split())
    foods = []
    for _ in range(N):
        row = map(int, input().split())
        foods.append(Food(*row))
    foods.sort(key=attrgetter('time_to_eat'))
    # 同じ料理の組を食べるなら時間のかかるものを後回しにしても結果は悪くならない

    dp = [-INF] * T
    dp[0] = 0
    # dp[time]:=timeに食べ終わる注文の仕方で得られる最大満足度

    ma = 0
    for food in foods:
        # これでフィニッシュの場合
        for time in reversed(range(T)):
            ma = max(ma, dp[time] + food.deliciousness)

        # まだ食べる場合
        for time in reversed(range(T - food.time_to_eat)):
            dp[time + food.time_to_eat] = max(
                dp[time + food.time_to_eat],
                dp[time] + food.deliciousness
            )

    print(ma)
    return


if __name__ == '__main__':
    solve_145e()

Submission status: Time Limit Exceeded

Solution code:
def solve_145e():
    from collections import namedtuple
    from operator import attrgetter

    Food = namedtuple('Food', 'time_to_eat deliciousness')
    INF = 3000 * 3000 + 1

    N, T = map(int, input().split())
    foods = []
    for _ in range(N):
        row = map(int, input().split())
        foods.append(Food(*row))
    foods.sort(key=attrgetter('time_to_eat'))
    # 同じ料理の組を食べるなら時間のかかるものを後回しにしても結果は悪くならない

    dp = [-INF] * T
    dp[0] = 0
    # dp[time]:=timeに食べ終わる注文の仕方で得られる最大満足度

    ma = 0
    for food in foods:
        # これでフィニッシュの場合
        for time in reversed(range(T)):
            ma = max(ma, dp[time] + food.deliciousness)

        # まだ食べる場合
        for time in reversed(range(T - food.time_to_eat)):
            dp[time + food.time_to_eat] = max(
                dp[time + food.time_to_eat],
                dp[time] + food.deliciousness
            )

    print(ma)
    return


if __name__ == '__main__':
    solve_145e()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    n,t=map(int,input().split())
    F=[tuple(map(int,input().split())) for _ in range(n)]

    dp1=np.zeros([n+1,t],dtype=np.int64)
    dp2=np.zeros([n+1,t],dtype=np.int64)
    for i in range(n):
        a1=F[i][0]
        b1=F[i][1]
        a2=F[n-i-1][0]
        b2=F[n-i-1][1]
        dp1[i+1][:a1]=dp1[i][:a1]
        dp1[i+1][a1:]=np.maximum(dp1[i][a1:],dp1[i][:-a1]+b1)
        dp2[i+1][:a2]=dp2[i][:a2]
        dp2[i+1][a2:]=np.maximum(dp2[i][a2:],dp2[i][:-a2]+b2)

    
    ans=0
    for i in range(n):
        b=F[i][1]
        for j in range(t):
            ans=max(dp1[i][j]+dp2[n-i-1][t-1-j]+b,ans)
    print(ans)          
  
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,t=map(int,input().split())
    F=[tuple(map(int,input().split())) for _ in range(n)]

    dp1=[[0]*t for _ in range(1+n)]
    dp2=[[0]*t for _ in range(1+n)]
    for i in range(n):
        a1=F[i][0]
        b1=F[i][1]
        a2=F[n-i-1][0]
        b2=F[n-i-1][1]
        for j in range(t):
            if j<a1:
                dp1[i+1][j]=dp1[i][j]
            else:
                dp1[i+1][j]=max(dp1[i][j],dp1[i][j-a1]+b1)
            
            if j<a2:
                dp2[i+1][j]=dp2[i][j]
            else:
                dp2[i+1][j]=max(dp2[i][j],dp2[i][j-a2]+b2)
    
    ans=0
    for i in range(n):
        b=F[i][1]
        for j in range(t):
            ans=max(dp1[i][j]+dp2[n-i-1][t-1-j]+b,ans)
    print(ans)          
  
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:


n, t = map(int, input().split())
time = []
ratio = []
delic = []
v = []
used = [False for i in range(n)]
for i in range(n):
    x, y = map(int, input().split())
    v.append((x, y))
    time.append((x, y))
    delic.append((y, x, i))
    ratio.append((y/x, x, y, i))


time.sort()

dp = [[0, 0] for i in range(t)]


for i in range(n):
    ti, d = time[i]
    for j in range(t-1, -1, -1):
        if j+ti < t:
            dp[j+ti][0] = max(dp[j+ti][0], dp[j][0]+d)
            dp[j+ti][1] = max(dp[j+ti][1], dp[j][1]+d)
        dp[j][1] = max(dp[j][1], dp[j][0]+d)

print(dp[t-1][1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    N,T = map(int,input().split())
    delay = 0
    food = []
    for _ in range(N):
        a,b = map(int,input().split())
        food.append((a,b))
        delay = max(delay,a)
        
    dp = [0 for _ in range(T+delay)]
    food.sort(key = itemgetter(0))
    
    for a,b in food:
        for i in reversed(range(T)):
            dp[i+a] = max(dp[i+a],dp[i]+b)

    print(max(dp[T:]))
    
if __name__ == "__main__":
    main()

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(reverse=True)
dp = [0] * (T + 1)

for a, b in AB:
    for t in range(T):
        x = dp[t+a]+b if t+a < T else b
        dp[t] = max(dp[t], x)

ans = dp[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    dp = [0] * (T + 1)
    for a, b in sorted(zip(A, B), reverse=True):
        for t in range(T):
            dp[t] = max(dp[t],
                        b + (dp[t+a] if t + a < T else 0))
    return max(dp)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    print(solve(N, T, A, B))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
N,T=map(int,input().split())

l=[]
for _ in range(N):
    a,b=map(int,input().split())
    l.append([a,b])

l.sort()

dp=[-1]*(6001)
dp[0]=0

for cand in l:
    for i in range(T)[::-1]:
        if dp[i]!=-1:
            dp[i+cand[0]]=max(dp[i+cand[0]],dp[i]+cand[1])
print(max(dp))