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: Wrong Answer

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():
    N, T = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    A = [0] * (N + 1)
    B = [0] * (N + 1)
    for i in range(N):
        A[i + 1], B[i + 1] = AB[i]

    a_max = max(A)
    t_max = T - 1 + a_max
    dp = [[0 for _ in range(t_max + 1)] for _ in range(N + 1)]

    for i in range(N):
        for j in range(t_max + 1):
            if 0 <= (j - A[i + 1]) and (j - A[i + 1]) < T:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j], dp[i][j - A[i + 1]] + B[i + 1])
            else:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

    ans = 0
    for d in dp:
        ans = max(ans, max(d))

    print(ans)

    # for i in range(t_max + 1):
    #     print("{:03},".format(i), end='')
    # print('')
    # for d in dp:
    #     for a in d:
    #         print("{:03},".format(a), end='')
    #     print('')


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():
    N, T = map(int, input().split())
    A = [0] * (N + 1)
    B = [0] * (N + 1)
    for i in range(1, N + 1):
        a, b = map(int, input().split())
        A[i], B[i] = a, b

    A.sort()
    a_max = max(A)
    t_max = T - 1 + a_max
    dp = [[0 for _ in range(t_max + 1)] for _ in range(N + 1)]

    for i in range(N):
        for j in range(t_max + 1):
            if 0 <= (j - A[i + 1]) and (j - A[i + 1]) < T:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j], dp[i][j - A[i + 1]] + B[i + 1])
            else:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

    ans = 0
    for d in dp:
        ans = max(ans, max(d))

    print(ans)

    # for i in range(t_max + 1):
    #     print("{:03},".format(i), end='')
    # print('')
    # for d in dp:
    #     for a in d:
    #         print("{:03},".format(a), end='')
    #     print('')


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():
    N, T = map(int, input().split())
    A = [0] * (N + 1)
    B = [0] * (N + 1)
    for i in range(1, N + 1):
        a, b = map(int, input().split())
        A[i], B[i] = a, b

    a_max = max(A)
    t_max = T - 1 + a_max
    dp = [[0 for _ in range(t_max + 1)] for _ in range(N + 1)]

    for i in range(N):
        for j in range(t_max + 1):
            if 0 <= (j - A[i + 1]) and (j - A[i + 1]) < T:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j], dp[i][j - A[i + 1]] + B[i + 1])
            else:
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

    ans = 0
    for d in dp:
        ans = max(ans, max(d))

    print(ans)

    # for i in range(t_max + 1):
    #     print("{:03},".format(i), end='')
    # print('')
    # for d in dp:
    #     for a in d:
    #         print("{:03},".format(a), end='')
    #     print('')


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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))
    
    dp = [[0] * (T+1) for _ in range(N)]

    ans = 0
    for i in range(N-1):
        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])
        
        dp[i+1][T] = dp[i+1][T-1] + AB[i+1][1]
        ans = max(ans, dp[i+1][T])
    
    print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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))
    
    dp = [[0] * (T+1) for _ in range(N)]

    ans = 0
    for i in range(N-1):
        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])
        
        dp[i+1][T] = dp[i+1][T-1] + AB[i+1][1]
        ans = max(ans, dp[i+1][T])
        #print(ans)
    
    print(dp[N-1][T])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

    for i in range(N):
        w_i, v_i = AB[i]
        for j in range(T+1):
            if j < 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])
                
            else:
                dp[i+1][j] = max(dp[i][j-1] + v_i, dp[i][j])

    print(dp[N][T])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n,t = map(int,input().split())
s = []
dp = np.full((n+1,t),0)
for _ in range(n):
    a,b = map(int,input().split())
    s.append([a,b])
s.sort()
ans = 0
#dp[i+1][j] .. i番目までのものから時間の総和がt以下となる時
for i in range(n):
    time = s[i][0]
    reward = s[i][1]
    ans = max(ans,np.max(dp[:i+1,:])+reward) #それを最後に食した場合答えとなる
    for j in range(t):
        if time > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],dp[i][j-time]+reward)
print(int(ans),dp)

Submission status: Wrong Answer

Solution code:
#dp[n][t]=max(dp[n-1][t],dp[n-1][t-A[n]]+B[n])
#dp[0][t]=0, dp[n][0]=0,0<=t<=T+max(B)-1, 0<=n<=N
def solve():
    N, T = map(int, input().split())
    A = [0]*N
    B = [0]*N
    for i in range(N):
        A[i],B[i] = map(int, input().split())
    dp = [[0]*(T+max(A)+1) for _ in range(N+1)]
    for n in range(1,N+1):
        for t in range(1,T+max(A)):
            dp[n][t]=dp[n-1][t]
            if t>=A[n-1] and t<T+A[n-1]:
                dp[n][t]=max(dp[n][t],dp[n-1][t-A[n-1]]+B[n-1])
    ans = max(dp[N])
    
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
#dp[n][t]=max(dp[n-1][t],dp[n-1][t-A[n]]+B[n])
#dp[0][t]=0, dp[n][0]=0,0<=t<=T+max(B)-1, 0<=n<=N
def solve():
    N, T = map(int, input().split())
    A = [0]*N
    B = [0]*N
    for i in range(N):
        A[i],B[i] = map(int, input().split())
    dp = [[0]*(T+max(B)+1) for _ in range(N+1)]
    for n in range(1,N+1):
        for t in range(1,T+max(B)):
            dp[n][t]=dp[n-1][t]
            if t>=A[n-1] and t<T+A[n-1]:
                dp[n][t]=max(dp[n][t],dp[n-1][t-A[n-1]]+B[n-1])
    ans = max(dp[N])
    
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,T = LI()
    A = [0]; B = [0]
    for _ in range(N):
        a,b = LI()
        A.append(a); B.append(b)
    dp = [[0] * (T+1) for _ in range(N+1)]

    for i in range(1,N+1):
        for j in range(1,T+1):
            if j == T:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+B[i])
                continue
            if j < A[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-A[i]]+B[i])
    print(dp[-1][T])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,T = LI()
    A = [0]; B = [0]
    for _ in range(N):
        a,b = LI()
        A.append(a); B.append(b)
    dp = [[0] * (T+1) for _ in range(N+1)]

    for i in range(N+1):
        for j in range(T+1):
            if j == T:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+B[i])
                continue
            if j < A[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-A[i]]+B[i])
    print(dp[-1][T])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from operator import itemgetter

    n, t = list(map(int, readline().split()))
    mat = [list(map(int, readline().split())) for _ in range(n)]
    mat.sort(key=itemgetter(0))
    dp = [[0] * t for _ in range(n + 1)]
    ans = 0

    for dish, vec in enumerate(mat, 1):
        a = vec[0]
        b = vec[1]
        for time, val in enumerate(dp[dish - 1]):
            if time + a >= t:
                ans = max(ans, val + b)
            else:
                dp[dish][time + a] = max(dp[dish - 1][time + a], val + b)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N, T = map(int, input().split())

menu = []
maxi = -1
maxb = 0
maxba = 3001
for i in range(N):
    a, b = map(int, input().split())
    menu.append((a, b))
    if b > maxb:
        maxb = b
        maxba = a
        maxi = i
    elif b == maxb and a < maxba:
        maxba = a
        maxi = i
menu.remove((maxba, maxb))

dp = np.zeros((N-1, T-1), dtype='int64')

for i in range(N-1):
    ai, bi = menu[i]
    dp[i][:ai] = dp[i-1][:ai] # 時間が足りないので注文しない
    dp[i][ai:] = np.fmax(
        dp[i-1][ai:], # 何も注文しない
        dp[i-1][:-ai] + bi # 注文した場合, ai分かかっても大丈夫な範囲から取得
    )

print(dp[N-2][T-2] + maxb)

Submission status: Wrong Answer

Solution code:
n,t=map(int,input().split())
food=[]
for i in range(n):
    a,b=map(int,input().split())
    food.append([b,a])
food.sort(reverse=True)
dp=[[0 for i in range(t)] for j in range(n)]
food.sort(reverse=True)
dp[0][0]=food[0][0]
food=food[1:]

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

print(max(dp[-1]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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

data.sort(key=lambda x: x[0])
A = [d[0] for d in data]
B = [d[1] for d in data]

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

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

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

t = T-1
items = []

# print(dp[N])
# print(used)

for i in list(range(1, N+1))[::-1]:
    val = used[i][t]
    if val>0:
        items.append(i-1)
        t -= val

# print(items)
if len(items) == N:
    print(dp[N][T - 1])
    sys.exit()

a = [b for idx, b in enumerate(B) if idx not in items]
print(dp[N][T-1] + max(a))

Submission status: Wrong Answer

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

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

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]*T for _ in range(N+1)]

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

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

t = T-1
items = []

# print(dp[N])
# print(used)

for i in list(range(1, N+1))[::-1]:
    val = used[i][t]
    if val>0:
        items.append(i-1)
        t -= val

# print(items)
if len(items) == N:
    print(dp[N][T - 1])
    sys.exit()

a = [b for idx, b in enumerate(B) if idx not in items]
print(dp[N][T-1] + max(a))

Submission status: Wrong Answer

Solution code:



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


"""
最後に食べる料理は時刻Tを超えても食べていてOKなので、時刻Tの時点で、食べるのに必要な時間が長くても得点の高いものを食べればよい
最後に食べるやつ x N-1品からi番目まで選べる時 x T-1分までのうちt分までに食べ終えて得られる最大のおいしさ
でDPをやると、O(N*N*T)で間に合わない

↑は最後に食べるものを軸に考えたDPだが、実際の所、その後ろの「N-1品～T-1までに食べ終えて得られる最大のおいしさ」を軸にしてみると、
この「」の後に食べる候補で全体の美味しさを最大化できるのは、残りの中で最も美味しいものである。
なので、最後に食べるもののループは実際は必要ない
これでO(N*T)程度になるので間に合う
"""


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

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

ans = 0

for i in range(N):
    tmp = 0
    if i < N-1:
        for j in range(i+1, N):
            tmp = max(tmp, B[j])

    ans = max(ans, dp[i+1][-1] + tmp)


print(ans)

Submission status: Wrong Answer

Solution code:



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


"""
最後に食べる料理は時刻Tを超えても食べていてOKなので、時刻Tの時点で、食べるのに必要な時間が長くても得点の高いものを食べればよい
最後に食べるやつ x N-1品からi番目まで選べる時 x T-1分までのうちt分までに食べ終えて得られる最大のおいしさ
でDPをやると、O(N*N*T)で間に合わない

↑は最後に食べるものを軸に考えたDPだが、実際の所、その後ろの「N-1品～T-1までに食べ終えて得られる最大のおいしさ」を軸にしてみると、
この「」の後に食べる候補で全体の美味しさを最大化できるのは、残りの中で最も美味しいものである。
なので、最後に食べるもののループは実際は必要ない
これでO(N*T)程度になるので間に合う
"""


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

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

ans = 0

for i in range(N):
    if i < N-1:
        p = dp[i+1][-1] + max(B[i+1:])
    else:
        p = dp[i+1][-1]
    ans = max(ans, p)


print(ans)

Submission status: Wrong Answer

Solution code:



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


"""
最後に食べる料理は時刻Tを超えても食べていてOKなので、時刻Tの時点で、食べるのに必要な時間が長くても得点の高いものを食べればよい
最後に食べるやつ x N-1品からi番目まで選べる時 x T-1分までのうちt分までに食べ終えて得られる最大のおいしさ
でDPをやると、O(N*N*T)で間に合わない

↑は最後に食べるものを軸に考えたDPだが、実際の所、その後ろの「N-1品～T-1までに食べ終えて得られる最大のおいしさ」を軸にしてみると、
この「」の後に食べる候補で全体の美味しさを最大化できるのは、残りの中で最も美味しいものである。
なので、最後に食べるもののループは実際は必要ない
これでO(N*T)程度になるので間に合う
"""


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

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

ans = 0

for i in range(N):
    if i < N-1:
        p = dp[i+1][-1] + max(B[i+1:])
    else:
        p = dp[i+1][j]
    ans = max(ans, p)


print(ans)

Submission status: Wrong Answer

Solution code:



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


"""
最後に食べる料理は時刻Tを超えても食べていてOKなので、時刻Tの時点で、食べるのに必要な時間が長くても得点の高いものを食べればよい
最後に食べるやつ x N-1品からi番目まで選べる時 x T-1分までのうちt分までに食べ終えて得られる最大のおいしさ
でDPをやると、O(N*N*T)で間に合わない

↑は最後に食べるものを軸に考えたDPだが、実際の所、その後ろの「N-1品～T-1までに食べ終えて得られる最大のおいしさ」を軸にしてみると、
この「」の後に食べる候補で全体の美味しさを最大化できるのは、残りの中で最も美味しいものである。
なので、最後に食べるもののループは実際は必要ない
これでO(N*T)程度になるので間に合う
"""


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

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

ans = 0

for i in range(N):
    if i < N-1:
        p = dp[i+1][-1] + max(B[i+1:])
    else:
        p = dp[i+1][j]
    ans = max(ans, p)


print(ans)

Submission status: Wrong Answer

Solution code:
#All-you -can -eat
N,T=map(int,input().split())
d=[]

for _ in range(N):
    a,b=map(int,input().split())
    d.append((a,b))
d.sort(key=lambda x:x[1])
dp=[[0 for i in range(T+1)] for j in range(N+1)]
#dp[N][T]=0番目からN番目まで見て、最後の食い終わりがT分の時の、考えうる最大の満足度
for i in range(N-1):
    time,value=d[i]
    for j in range(time,T):
        #i=value....T
        dp[i+1][j]=max(dp[i][j],dp[i][j-time]+value)
time,value=d[-1]

#最大の満足度はdp[N][i](0<=i<T)の時の最大値
ans=0
for i in range(T):
    ans=max(ans,dp[N-1][i]+value)
print(ans)

Submission status: Wrong Answer

Solution code:

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:

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

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

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

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

Submission status: Wrong Answer

Solution code:

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

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

AB = sorted(AB, key = lambda x: x[1])

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

Submission status: Wrong Answer

Solution code:

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

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

AB = sorted(AB, key = lambda x: x[1])

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

Submission status: Wrong Answer

Solution code:

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

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

AB = sorted(AB, key = lambda x: x[1])

for i in range(N-1):
    for j in range(T-1,-1, -1):
        if j+AB[i][0] <= T-1:
            kari2 = Dp[j] + AB[i][1]
            if  Dp[j+AB[i][0]]< kari2:
                Dp[j+AB[i][0]] = kari2
                kari = used_ab[j].copy()
                kari.remove(i)
                used_ab[j+AB[i][0]] = kari
print(Dp[-2]+AB[-1][1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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


for i in range(N):
    for j in range(T-1,-1, -1):
        if j+AB[i][0] <= T-1:
            if Dp[j+AB[i][0]] < Dp[j] + AB[i][1]:
                Dp[j+AB[i][0]] = Dp[j] + AB[i][1]
                kari = used_ab[j].copy()
                kari.add(i)
                used_ab[j+AB[i][0]] = kari

answer = 0
for i in range(T):
    max_amari = 0
    for j in range(N):
        if j not in used_ab[i] and max_amari < AB[j][1]:
            max_amari = AB[j][1]
    if Dp[i]+max_amari > answer:
        answer = Dp[i]+max_amari

print(answer)

Submission status: Wrong Answer

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

Dp = [-10e+100 for _ in range(T+1)]

Dp[0] = 0

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

print(max(Dp))

Submission status: Wrong Answer

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

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

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

print(max(Dp))

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
orders = []
for i in range(n):
    a,b = map(int,input().split())
    orders.append([a,b])

orders.sort(key=lambda x:(x[0],-x[1]))
# print(orders)

dp = [[-1e10 for i in range(t+1)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for i,od in enumerate(orders):
    for j in range(t):
        nt = j+od[0]
        if nt > t-1:
            nt = t
        temp = max(dp[i][j]+od[1],dp[i][nt])
        dp[i+1][nt] =temp

# for l in dp:
#     print(l[:11])
# print(dp[-1])
print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
orders = []
for i in range(n):
    a,b = map(int,input().split())
    orders.append([a,b])

orders.sort(key=lambda x:(x[0],-x[1]))
# print(orders)

dp = [[-1e10 for i in range(t+1)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for i,od in enumerate(orders):
    for j in range(t):
        nt = j+od[0]
        if nt > t-1:
            nt = t
        temp = max([dp[i+1][nt],dp[i][j]+od[1],dp[i][nt]])
        dp[i+1][nt] =temp

# for l in dp:
#     print(l[:11])
# print(dp[-1])
print(max(max(dp[-1]),0))

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
orders = []
for i in range(n):
    a,b = map(int,input().split())
    orders.append([a,b])

orders.sort(key=lambda x:(x[0],-x[1]))
# print(orders)

dp = [[-1e10 for i in range(t+1)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for i,od in enumerate(orders):
    for j in range(t):
        nt = j+od[0]
        if nt > t-1:
            nt = t
        temp = max([dp[i+1][nt],dp[i][j]+od[1],dp[i][nt]])
        dp[i+1][nt] =temp

# for l in dp:
#     print(l[:11])
# print(dp[-1])
print(max(dp[-1]))

Submission status: Wrong Answer

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

print(ans)

Submission status: Wrong Answer

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

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: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
ma = ab[-1][1]
n -= 1
ab = ab[:-1]
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])
point = 0
for i in range(1,n+1):
    point = max(point,dp[i][t-1]+ma)
print(point)

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
ma = ab[-1][1]
n -= 1
ab = ab[:-1]
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])

point = 0
for i,(ti,vi) in enumerate(ab):
    point = max(point,ma+vi)
print(point)

Submission status: Wrong Answer

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

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,(ti,vi) in enumerate(ab):
    ma = max(ma,dp[i][t-1]+vi)
print(ma)

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
point = ab[-1][1]
n -= 1
t -= 1
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])
print(max(dp[-1])+point)