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
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# youk_library(debug)
def list_to_tsv_string(target: [], limit_row: int = 0, limit_column: int = 0):
    import csv

    # 行列を制限内に縮める
    if limit_row is not 0:
        target = target[:limit_row]
    if limit_column is not 0:
        target = [i[:limit_column] for i in target]

    # 行番号、列番号を追加
    # 行番号
    target = [[cnt] + i for cnt, i in enumerate(target)]
    # 列番号
    work = [i for i in range(len(target[0]))]
    target.insert(0, work)
    # tsv出力
    with open("temp.txt", "w", newline="") as f:
        writer = csv.writer(f, delimiter="\t")
        writer.writerows(target)


# 実装を行う関数
def resolve(test=""):
    try:
        n, t = map(int, input().split())
        ab_s = [list(map(int, input().split())) for i in range(n)]

        # DPの鉄則的? 「カスタム添え字として使用する」要素でソート。
        # ※本問題の場合、カスタム添え字は「使用する時間」。この昇順でソート。
        ab_s.sort(key=lambda xx: [xx[0]])

        # dp[料理を先頭Xまで見た:0~3000][使用する時間(累計):0~6000] = おいしさの最大値(-1=存在しないパターン)
        dp = [[-1 for j in range(6000 + 1)] for j in range(3000 + 1)]

        # dp初期化(料理を何も食べない場合、おいしさは0。
        dp[0][0] = 0

        # ------------
        # dp
        # ------------
        # 先頭からi個選ぶループ(添え字の個数-1回)
        for i in range(3000):
            # 最後の要素まで検証したならDP終了
            if len(ab_s) == i:
                break

            # 行の初期化(前の行を現在の行にコピー)
            dp[i + 1] = dp[i].copy()

            # 検証対象の情報を取り出し
            time, delicious = ab_s[i]

            # カスタム添え字ループ(カスタム添え字の個数-1回)
            for j in range(6000):
                # 制限時間を超えたら要素の検証を終える。次の要素へ。
                if j > t - 1:
                    break

                # 0未満(存在しないパターン)は検証しない
                if dp[i][j] < 0:
                    continue

                # 最適解を取得
                val = max(dp[i + 1][j + time], dp[i][j] + delicious)

                # 最適解を反映
                dp[i + 1][j + time] = val

        # 結果を出力
        print(max(dp[i]))


    except IndexError as err:
        print("インデックスエラー:", err.args[0])


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    # 自作テストパターン
    def test_original1(self):
        test_input = """3 10
1 10
3000 20
1 20"""
        output = """50"""
        self.assertIO(test_input, output)

    def test_original2(self):
        test_input = """4 10
3 13
4 14
5 20
4 21"""
        output = """55"""
        self.assertIO(test_input, output)

    def test_input_1(self):
        test_input = """2 60
10 10
100 100"""
        output = """110"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """3 60
10 10
10 20
10 30"""
        output = """60"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """3 60
30 10
30 20
30 30"""
        output = """50"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25"""
        output = """145"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main(verbosity=2)

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

#######################################################################
# ナップサック
# 重さ：Wー10**5くらい
# 価値：N*max_Viー10**11くらい
# dp[w]:wの重さで可能な最大の価値
#   dp[w]とdp[w-wi]+vi(i番目のアイテムをとる場合)との大きいほうで更新
#######################################################################

#import numpy as np

n, t = map(int, input().split())
dp = [0] * (t+1)
#dp = np.array(dp)
for _ in range(n):
    w_, v_ = map(int, input().split())
    for i in range(1,t+1):
        dp[max(0,i-w_)] = max(dp[max(0,i-w_)], dp[i] + v_)
#    dp[:w_] = np.maximum(dp[w:_], dp[:-w_] + v_)
#    print(dp)
print(dp[0])

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [[[0] * T for _ in range(N + 1)] for _ in range(2)]  # (最後の注文を使ったか, i未満までみた, T)
for i in range(1, N + 1):
    a, b = AB[i-1]
    for t in range(T):
        if t-a>=0:
            dp[0][i][t] = max(dp[0][i - 1][t], dp[0][i - 1][t-a] + b)
        else:
            dp[0][i][t] = dp[0][i - 1][t]
        dp[1][i][t] = max(dp[1][i - 1][t], dp[0][i - 1][t] + b)

print(dp[1][N][T-1])

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
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())
dp1=[[0]*(t-1) for _ in range(n+1)]
dp2=[[0]*(t-1) for _ in range(n+1)]
for i in range(n):
  for j in range(t-1):
    if j>=a[i]:dp1[i+1][j]=max(dp1[i][j],dp1[i][j-a[i]]+b[i])
    else:dp1[i+1][j]=dp1[i][j]
for i in range(n,0,-1):
  for j in range(t-1):
    if j>=a[i-1]:dp2[i-1][j]=max(dp2[i][j],dp2[i][j-a[i-1]]+b[i-1])
    else:dp2[i-1][j]=dp2[i][j]
ans=0
for i in range(n):
  for j in range(t-1):
    ans=max(ans,dp1[i][j]+dp2[i+1][t-j-2]+b[i])
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import*
from copy import*
n,t=map(int,input().split())
h=[]
q=[0]*n
for i in range(n):
  a,b=map(int,input().split())
  heappush(h,(-b,a,i))
  q[i]=b
ans=0
for i in range(n):
  hq=copy(h)
  tc=t-1
  cnt=q[i]
  while hq:
    b,a,j=heappop(hq)
    if j==i or tc-a<0:continue
    cnt-=b
    tc-=a
  ans=max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)



def solve():
    n, t = getList()
    li = []
    for i in range(n):
        li.append(getList())

    li.sort(key=lambda x: 30000 * x[0] + x[1])
    dp = [0] * (t + 1)
    ans = 0
    for a, b in li:
        tmp = copy.copy(dp)
        ans = max(ans, dp[-1] + b)
        for idx, dd in enumerate(dp):
            # tmp[idx] = max(tmp[idx], dd)
            if idx + a <= t:
                tmp[idx + a] = max(dp[idx + a], dp[idx] + b)
        dp = tmp
        for j in range(len(dp) - 1):
            dp[j+1] = max(dp[j], dp[j+1])
    #     print(dp)
    # print(li)
    print(ans)





def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)



def solve():
    n, t = getList()
    li = []
    for i in range(n):
        li.append(getList())

    li.sort(key=lambda x: 30000 * x[0] - x[1])
    dp = [-1] * (t + 1)
    dp[0] = 0
    for a, b in li[:-1]:
        tmp = copy.copy(dp)
        for idx, dd in enumerate(dp):
            # tmp[idx] = max(tmp[idx], dd)
            if dd != -1 and idx + a <= t:
                tmp[idx + a] = max(dp[idx + a], dp[idx] + b)
        dp = tmp
        for j in range(len(dp) - 1):
            dp[j+1] = max(dp[j], dp[j+1])
        # print(dp)
    # print(li)
    print((dp[t-1]) + li[-1][1])





def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)



def solve():
    n, t = getList()
    li = []
    for i in range(n):
        li.append(getList())

    li.sort(key=lambda x: 30000 * x[1] + x[0])
    dp = [-1] * (t + 1)
    dp[0] = 0
    for a, b in li[:-1]:
        tmp = copy.copy(dp)
        for idx, dd in enumerate(dp):
            # tmp[idx] = max(tmp[idx], dd)
            if dd != -1 and idx + a <= t:
                tmp[idx + a] = max(dp[idx + a], dp[idx] + b)
        dp = tmp
        for j in range(len(dp) - 1):
            dp[j+1] = max(dp[j], dp[j+1])
        # print(dp)
    # print(li)
    print((dp[t-1]) + li[-1][1])





def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)



def solve():
    n, t = getList()
    li = []
    for i in range(n):
        li.append(getList())

    li.sort(key=lambda x: 30000 * x[1] + x[0])
    dp = [-1] * (t + 1)
    dp[0] = 0
    for a, b in li[:-1]:
        tmp = copy.copy(dp)
        for idx, dd in enumerate(dp):
            # tmp[idx] = max(tmp[idx], dd)
            if dd != -1 and idx + a <= t:
                tmp[idx + a] = max(dp[idx + a], dp[idx] + b)
        dp = tmp
    #     print(dp)
    # print(li)
    print(max(dp[:t-1]) + li[-1][1])





def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)



def solve():
    n, t = getList()
    li = []
    for i in range(n):
        li.append(getList())

    li.sort(key=lambda x: 30000 * x[1] + x[0])
    dp = [-1] * (t + 1)
    dp[0] = 0
    for a, b in li[:-1]:
        tmp = copy.copy(dp)
        for idx, dd in enumerate(dp):
            # tmp[idx] = max(tmp[idx], dd)
            if dd != -1 and idx + a <= t:
                tmp[idx + a] = max(dp[idx + a], dp[idx] + b)
        dp = tmp
    #     print(dp)
    # print(li)
    print(max(dp[:t]) + li[-1][1])





def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)



def solve():
    n, t = getList()
    li = []
    for i in range(n):
        li.append(getList())

    li.sort(key=lambda x: x[1])
    dp = [-1] * (t + 1)
    dp[0] = 0
    for a, b in li[:-1]:
        tmp = copy.copy(dp)
        for idx, dd in enumerate(dp):
            # tmp[idx] = max(tmp[idx], dd)
            if dd != -1 and idx + a <= t:
                tmp[idx + a] = max(dp[idx + a], dp[idx] + b)
        dp = tmp
    #     print(dp)
    # print(li)
    print(max(dp[:t]) + li[-1][1])





def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Wrong Answer

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

N,T = map(int, input().split())
R = []
for i in range(N):
  times, value = map(int, input().split())
  R.append((times, value))
  
R.sort(key=itemgetter(1,0), reverse=True) 
# DP1[i][j] = 1～i 番目の料理で j 分以内に完食できる美味しさの合計の最大値
# 0番目はT-1分に食べる、としてよい.美味しさ最大でかつ食べるのに一番時間がかかるもの
#print(R)
def solve2():
  #dp[i][w] i個目までを選んで、時間W以下で実現できる最大の価値
  dp = [-1] * (T)
  dp[0] = 0
  for i in range(1,N):
    w1,v1 = R[i]
    for w in range(T-1,-1,-1):
      if w-w1>=0 and dp[w-w1] >= 0:
        dp[w] = max(dp[w], dp[w-w1]+v1)
  ret = max(dp)
  return ret
      
print(solve2() + R[0][1])

Submission status: Wrong Answer

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

N,T = map(int, input().split())
R = []
for i in range(N):
  times, value = map(int, input().split())
  R.append((times, value))
  
R.sort(key=itemgetter(1,0), reverse=True) 
# DP1[i][j] = 1～i 番目の料理で j 分以内に完食できる美味しさの合計の最大値
# 0番目はT-1分に食べる、としてよい.美味しさ最大でかつ食べるのに一番時間がかかるもの
print(R)
def solve2():
  #dp[i][w] i個目までを選んで、時間W以下で実現できる最大の価値
  dp = [-1] * (T)
  dp[0] = 0
  for i in range(1,N):
    w1,v1 = R[i]
    for w in range(T-1,-1,-1):
      if w-w1>=0 and dp[w-w1] >= 0:
        dp[w] = max(dp[w], dp[w-w1]+v1)
  ret = max(dp)
  return ret
      
print(solve2() + R[0][1])

Submission status: Wrong Answer

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

N,T = map(int, input().split())
R = []
for i in range(N):
  times, value = map(int, input().split())
  R.append((times, value))
  
R.sort(key=itemgetter(1,0), reverse=True) 
# DP1[i][j] = 1～i 番目の料理で j 分以内に完食できる美味しさの合計の最大値
# 0番目はT-1分に食べる、としてよい.美味しさ最大でかつ食べるのに一番時間がかかるもの

def solve2():
  #dp[i][w] i個目までを選んで、時間W以下で実現できる最大の価値
  dp = [0] * (T+1)
  dp[0] = 0
  for i in range(1,N):
    w1,v1 = R[i]
    for w in range(T,-1,-1):
      if w-w1>=0:
        dp[w] = max(dp[w], dp[w-w1]+v1)
  ret = max(dp[:T])
  
  #print(dp[2900:2930])
  return ret
      
print(solve2() + R[0][1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, T = map(int, input().split())
dp = [0] * (T + 1)
for _ in range(N):
  a, b = map(int, input().split())
  for i in range(T - 1, -1, -1):
    if i + a < T: dp[i + a] = max(dp[i + a], dp[i] + b)
    else: dp[-1] = max(dp[-1], dp[i] + b) 
print(max(dp))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,t=map(int,input().split())
d=[[0]*t for i in range(n+1)]
ab=[list(map(int,input().split())) for _ in range(n)]
ab=sorted(ab,key=lambda x:x[1],reverse=True)
for j in range(t):
    d[1][j]=ab[0][1]
for i in range(1,n):
    a=ab[i-1][0]
    b=ab[i][1]
    for j in range(t):
        if j<a:
            d[i+1][j]=d[i][j]
        else:
            d[i+1][j]=max(d[i+1][j],d[i][j],d[i][j-a]+b)
print(d[-1][-1])

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
L = []
m = 0
for _ in range(n):
    a,b = map(int,input().split())
    m = max(b,m)
    L.append((a,b))
L.sort()
dp =[[0]*(t+m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(t+m+1):
        if j-L[i][0]>=0 and t>j-L[i][0]:
            dp[i+1][j] = max(dp[i][j],dp[i][j-L[i][0]]+L[i][1])
        else:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
ans = 0
for i in range(n+1):
    ans = max(ans,max(dp[i]))
print(dp)
print(ans)
#     L.append((b/a,a,b))
# L.sort(key = lambda x:(-x[0],x[1]))
# hq = []
# ans = []
# print(L)
# import heapq
# for c,a,b in L:
#     if a>=t:
#         heapq.heappush(hq,(-b,a,c))
#     else:
#         ans.append((b,a,c))
#         t-=a
# heapq.heapify(ans)
# if t ==0 and hq:
#     nb,nc,na = heapq.heappop(hq)
#     bb,bc,ba = heapq.heappop(ans)
#     if nb>bb:
#         heapq.heappush(ans,(-nb,nc,na))
#     else:
#         heapq.heappush(ans,(bb,b,c,ba))
# elif hq:
#     nb,nc,na = heapq.heappop(hq)
#     heapq.heappush(ans,(-nb,nc,na))
# res = 0
# for b,c,a in ans:
#     res += b
# print(ans)

Submission status: Wrong Answer

Solution code:
n, t = map(int, input().split())
dp = [0] * (t + 1)
ab = [tuple(map(int, input().split())) for _ in range(n)]
#ab.sort()
max_b = [0] * n
max_b[-1] = ab[-1][1]
for i in range(n - 1, 0, -1):
    max_b[i - 1] = max(ab[i - 1][1], max_b[i])
for i in range(n - 1):
    a, b = ab[i]
    for j in range(t - 1, a-1, -1):
        dp[j] = max(dp[j - a] + b, dp[j])
    dp[t] = max(dp[t], dp[t-1] + max_b[i + 1])
print(max(dp))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, t = list(map(int, input().split()))

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

ab.sort()
ab = [[0,0]] + ab
m_a = ab[-1][0]

# a = []
# b = []
# for i in range(n):
#     ai, bi = list(map(int, input().split()))
#     a.append(ai)
#     b.append(bi)

u = t + m_a

dp = [[(0, -1)] * (u+1) for _ in range(n+1)]
#print(len(dp))

for i in range(1, n+1):
    for j in range(u+1):
        if j - ab[i][0] < 0:
            #print(i, j, len(dp))
            dp[i][j] = dp[i-1][j]

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

m = 0
for j in range(t, u):
    w, k = dp[n][j]
    #print(w, k)
    if j - ab[k][1] < t:
        m = max(m, w)

print(m)

Submission status: Wrong Answer

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

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

# dp[i][j] = 1～i 番目の料理で j 分以内に完食できる美味しさの合計の最大値
dp = [ [0]*(T+1) for _ in range(N+1) ]

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

# for d in dp:
#   print(d)

ans = 0
for i in range(1, N):
  b = foods[i-1][1]
  ans = max(ans, dp[i][-1], dp[i-1][-2]+b)

print(max(ans, dp[-1][-1]))

Submission status: Wrong Answer

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

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

# dp1[t]: i番目の料理まででt分以内に食べれるものの美味しさ
# dp2[t]: i番目の料理まででt分以内に食べれるものの美味しさ (最後に食べる用のを選んだ仮定)

dp1 = np.zeros(T,dtype=int)
dp2 = np.zeros(T,dtype=int)

for a,b in meals:
    ndp1 = dp1.copy()
    ndp1[a:] = np.maximum(dp1[a:],dp1[:-a]+b)

    ndp2 = dp2.copy()
    ndp2[a:] = np.maximum(dp2[a:],dp2[:-a])
    ndp2 = np.maximum(ndp2,dp1+b)
    dp1,dp2 = ndp1,ndp2

print(ndp2[-1])

Submission status: Wrong Answer

Solution code:

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

X.sort(key=lambda x: -x[1])
dp = [[0] * T for _ in range(N + 1)]
for i in range(N):
    for j in range(T):
        if j == 0:
            dp[i + 1][j] = X[i][1]
        elif j >= X[i][0]:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - X[i][0]] + X[i][1])

print(max(max(v) for v in dp))

Submission status: Wrong Answer

Solution code:
def knapsack_weight(single=True):
    """
    重さが小さい時のナップサックDP
    :param single: True = 重複なし
    """
    """ dp[weight <= W] = 重さ上限を固定した時の最大価値 """
    dp_min = 0  # 総和価値の最小値
    dp = [dp_min] * (W + 1)

    for item in range(N):
        if single:
            S = range(W, weight_list[item] - 1, -1)
        else:
            S = range(weight_list[item], W + 1)
        for weight in S:
            if weight - weight_list[item] < T:
                dp[weight] = max2(dp[weight], dp[weight - weight_list[item]] + price_list[item])
    return max(dp[T:])

import sys
input = sys.stdin.readline


def max2(x, y):
    return x if x > y else y

def min2(x, y):
    return x if x < y else y


N, T = map(int, input().split())                                # N: 品物の種類 W: 重量制限

price_list = []
weight_list = []
for _ in range(N):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)

max_weight = max(weight_list)

W = T + max_weight - 1

print(knapsack_weight(single=True))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, t = map(int, input().split())
lst = [0 for _ in range(t)]
ans = 0
for _ in range(n):
    a, b = map(int, input().split())
    ans = max(ans, lst[-1] + b)
    for i in range(t - 1, a - 1, -1):
        lst[i] = max(lst[i], lst[i - a] + b)

print(ans)

Submission status: Wrong Answer

Solution code:
n, t = map(int, input().split())
lst = [0 for _ in range(t + 1)]

for _ in range(n):
    a, b = map(int, input().split())
    lst[-1] = max(lst[-1], lst[-2] + b)
    for i in range(t, a - 1, -1):
        lst[i] = max(lst[i], lst[i - a] + b)

print(lst[-1])

Submission status: Wrong Answer

Solution code:
n, t = map(int, input().split())
lst = [0 for _ in range(t + 1)]

for _ in range(n):
    a, b = map(int, input().split())
    lst[-1] = max(lst[-1], lst[-2] + b)
    for i in range(t - 1, a - 1, -1):
        lst[i] = max(lst[i], lst[i - a] + b)

print(lst[-1])

Submission status: Wrong Answer

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,T = IL()
data = ILL(N)


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

for i in range(1,N+1):
  tt,vv = data[i-1]
  for t in range(1,T):
    if t >= tt:
      dp[i][t] = max(dp[i-1][t], dp[i-1][t-tt]+vv)
    else:
      dp[i][t] = dp[i-1][t]
  dp[i][T] = max(dp[i-1][T], dp[i-1][T-1]+vv)
      
print(dp[-1][-1])