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
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import itertools
INF = float('inf')
MOD = 10**9+7

N, T = map(int, input().split())
AB = [None] * N
for i in range(N):
    AB[i] = list(map(int, input().split()))

dp1 = [[-INF]*(T+1) for i in range(N+1)]
dp1[0][0] = 0
for i in range(N):
    A, B = AB[i]
    for j in range(T+1):
        if A <= j:
            tmp = dp1[i][j-A]+B
            if dp1[i][j] < tmp:
                dp1[i+1][j] = tmp
            else:
                dp1[i+1][j] = dp1[i][j]
        else:
            dp1[i+1][j] = dp1[i][j]

AB = AB[::-1]
dp2 = [[-INF]*(T+1) for i in range(N+1)]
dp2[0][0] = 0
for i in range(N):
    A, B = AB[i]
    for j in range(T+1):
        if A <= j:
            tmp = dp2[i][j-A]+B
            if dp2[i][j] < tmp:
                dp2[i+1][j] = tmp
            else:
                dp2[i+1][j] = dp2[i][j]
        else:
            dp2[i+1][j] = dp2[i][j]

for i in range(N):
    for j in range(1, T+1):
        if dp1[i][j] < dp1[i][j-1]:
            dp1[i][j] = dp1[i][j-1]

for i in range(N):
    for j in range(1, T+1):
        if dp2[i][j] < dp2[i][j-1]:
            dp2[i][j] = dp2[i][j-1]


AB = AB[::-1]
ans = max(dp1[N][T], dp1[N-1][T-1]+AB[-1][1], dp2[N-1][T-1]+AB[0][1])
for i in range(1, N-1):
    B = AB[i][1]
    for j in range(T):
        tmp = dp1[i-1][j]+B+dp2[N-i-1][T-j-1]
        if ans < tmp:
            ans = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
#print(l)
ans=[]
for k in range(1,n+1):
    dp=[[0]*(t) for _ in range(n)]
    for i in range(1,k):
        for j in range(t):
            if j-l[i-1][0]>0:
                dp[i][j]=max(dp[i-1][j-l[i-1][0]]+l[i-1][1],dp[i-1][j])
            else:
                dp[i][j]=dp[i-1][j]
    ans.append(dp[k-n-1][-1]+l[k-1][1])
    #print(dp[k-n-1])
#print(q)
print(max(ans))

Submission status: Wrong Answer

Solution code:
N,T=[int(s) for s in input().split()]
lst=[[int(s) for s in input().split()] for i in range(N)]
result=[]
for k in range(N):
  ls=[e for e in lst]
  y=ls.pop(k)
  dp=[0 for i in range(T-1)]
  for i in range(N-1):
    a,b=ls[i]
    for t in range(T-1-a):
      s=T-t-2-a
      x=dp[s]+b
      if dp[s+a]<x:
        dp[s+a]=x
  result.append(dp[-1]+y[1])
print(max(result))

Submission status: Wrong Answer

Solution code:
# dp[i][t_sum]: i番目までの品物で時間がt_sumを超えないように選んだときの、満足度の総和の最大値
N, T = map(int, input().split())
items = [tuple(map(int, input().split())) for i in range(N)]

dp1 = [[0 for t_sum in range(T+1)] for i in range(N+2)]
dp2 = [[0 for t_sum in range(T+1)] for i in range(N+2)]

for i in range(N):
    for t_sum in range(T):

        # これは配るDP
        if t_sum+items[i][0] <= T:
            dp1[i+1][t_sum+items[i][0]] = max(dp1[i+1][t_sum+items[i][0]],
                                              dp1[i][t_sum]+items[i][1])
        # i-1番目の品物を選ばない場合
        dp1[i+1][t_sum] = max(dp1[i+1][t_sum], dp1[i][t_sum])

        # これは配るDP
        if t_sum+items[N-1-i][0] <= T:
            dp2[N-1-i][t_sum+items[N-1-i][0]] = max(dp2[N-1-i][t_sum+items[N-1-i][0]],
                                                    dp2[N-i][t_sum]+items[N-1-i][1])
        # i-1番目の品物を選ばない場合
        dp2[N-1-i][t_sum] = max(dp2[N-1-i][t_sum], dp2[N-i][t_sum])
# print(dp[N])

ans = 0
for i in range(N):
    for t in range(T):
        ans = max(ans, dp1[i-1][t]+dp2[i+1][T-1-t]+items[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
#入力
N, T = [int(x)for x in input().split()]
ab=[[0]*2 for _ in range(N)]
for i in range(N): #N=3000
    ab[i]=[int(x) for x in input().split()]

ab.sort(key=lambda j:j[1]) #長さでソートする
T=T-1 #最後の注文は別枠にする

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

for i in range(N-1): #N=3000 9*10^6 なんでTLEするんだ？
    for j in range(T):#T=3000 内部計算量は最大でも定数で3
        if j < ab[i][0]:
            dp[i][j] = dp[i - 1][j]
        else:
            if(dp[i - 1][j]<  dp[i - 1][j - ab[i][0]] + ab[i][1]):
                dp[i][j] =  dp[i - 1][j - ab[i][0]] + ab[i][1]
            else:
                dp[i][j] = dp[i - 1][j]

print(dp[N-2][T-1] + ab[N-1][1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, t = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort()
dp = [[0 for j in range(t+1)] for i in range(n+1)]

for i in range(n):
    for j in range(t):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    for j in range(t):
        if j < t:
            next = min(j + ab[i][0], t)
            dp[i+1] [next] = max(dp[i+1][next], dp[i][j] + ab[i][1])
print(max(dp[n]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
# from bisect import *
# from collections import *
# from heapq import *
# import functools
# import itertools
# import math
INF = float('inf')
MOD = 10**9+7

N, T = map(int, input().split())
AB = [None] * N
for i in range(N):
    AB[i] = list(map(int, input().split()))

dp1 = [[-INF]*(T+1) for i in range(N+1)]
dp1[0][0] = 0
for i in range(N):
    A, B = AB[i]
    for j in range(T+1):
        if A <= j:
            dp1[i+1][j] = max(dp1[i][j], dp1[i][j-A]+B)
        else:
            dp1[i+1][j] = dp1[i][j]

AB = AB[::-1]
dp2 = [[-INF]*(T+1) for i in range(N+1)]
dp2[0][0] = 0
for i in range(N):
    A, B = AB[i]
    for j in range(T+1):
        if A <= j:
            dp2[i+1][j] = max(dp2[i][j], dp2[i][j-A]+B)
        else:
            dp2[i+1][j] = dp2[i][j]

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

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

AB = AB[::-1]
ans = max(dp1[N][T], dp1[N-1][T-1]+AB[-1][1], dp2[N-1][T-1]+AB[0][1])
for i in range(1, N-1):
    B = AB[i][1]
    for j in range(T):
        ans = max(ans, dp1[i-1][j]+dp2[N-i-1][T-j-1]+B)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, t = list(map(int, readline().split()))
    ab = []
    for i in range(n):
        a, b = list(map(int, readline().split()))
        ab.append([a, b])
    ab.sort(key=lambda x: x[1], reverse=True)
    ls = [0] * t
    for i in range(1, n):
        a, b = ab[i]
        for j in range(t-a-1, -1, -1):
            ls[j+a] = max(ls[j+a], ls[j] + b)
    print(max(ls) + ab[0][1])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, t = list(map(int, readline().split()))
    ab = []
    for i in range(n):
        a, b = list(map(int, readline().split()))
        ab.append([a, b])
    ab.sort(key=lambda x: x[1], reverse=True)
    ls = [0] * (t + 1)
    for i in range(1, n):
        a, b = ab[i]
        for j in range(t-a, -1, -1):
            ls[j+a] = max(ls[j+a], ls[j] + b)
    print(max(ls) + ab[0][1])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, t = list(map(int, readline().split()))
    ab = []
    for i in range(n):
        a, b = list(map(int, readline().split()))
        ab.append([a, b])
    ab.sort(key=lambda x: x[0], reverse=True)
    ls = [0] * (t + 1)
    for i in range(1, n):
        a, b = ab[i]
        for j in range(t-a-1, -1, -1):
            ls[j+a] = max(ls[j+a], ls[j] + b)
    print(max(ls) + ab[0][1])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#入力
N, T = map(int, input().split())
ab=[[0]*2 for _ in range(N)]
for i in range(N):
    ab[i]=[int(x) for x in input().split()]

ab.sort(key=lambda j:j[1]) #長さでソートする
T=T-1 #最後の注文は別枠にする

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

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

print(dp[N-2][T-1] + ab[N-1][1])

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, t = list(map(int, readline().split()))
    ab = []
    for i in range(n):
        a, b = list(map(int, readline().split()))
        ab.append([a, b])
    ab.sort(key=lambda x: x[1], reverse=True)
    ls = [0] * (t + 1)
    for i in range(1, n):
        a, b = ab[i]
        for j in range(t-a-1, -1, -1):
            ls[j+a] = max(ls[j+a], ls[j] + b)
    print(max(ls) + ab[0][1])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

n,t = _ia()
ab = []
imax = -1
amax = -1
bmax = -1
for i in range(n):
    _a,_b = _ia()
    ab.append((_a,_b))
    if bmax<0 or (_b>=bmax and _a>ab[imax][0]):
        imax = i
        amax = _a
        bmax = _b
#
dp = [ [0]*(t+1) for _ in range(n+1) ]
for i in range(n):
    a,b = ab[i]
    if i==imax: b=0
    
    prev = dp[i]
    dnew = dp[i+1]
    for atot in range(t+1):
        if atot>=a:
            dnew[atot] = max(prev[atot],prev[atot-a]+b)
        else:
            dnew[atot] = prev[atot]
#
print(max(dnew[t-1]+bmax,dnew[t]))

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
T=T-1
ab=[[0]*2 for _ in range(N)]

for i in range(N):
    ab[i]=[int(x) for x in input().split()]

ab.sort(key=lambda j:j[1])

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

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

print(dp[N-2][T-1] + ab[N-1][1])

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
dishes = [tuple(map(int, input().split())) for _ in range(N)]
dishes = sorted(dishes)
dp = [[-1 for j in range(T+3001)] for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    a, b = dishes[i]
    for j in range(T+3001):
        if j < a or T+a <= j:
            dp[i+1][j] = dp[i][j]
        else:
            if dp[i][j-a] < 0: continue
            dp[i+1][j] = max(dp[i][j], dp[i][j - a] + b)
print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
dishes = [tuple(map(int, input().split())) for _ in range(N)]
dishes = sorted(dishes)
dp = [[-1 for j in range(T+3001)] for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(N):
    a, b = dishes[i]
    for j in range(a):
        dp[i+1][j] = dp[i][j]
    for j in range(a, T+a):
        if dp[i][j-a] < 0: continue
        dp[i+1][j] = max(dp[i][j], dp[i][j - a] + b)
    for j in range(T+a, T+3001):
        dp[i+1][j] = dp[i][j]
print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
N, T = map(int, input().split())
T=T-1
ab=[[0]*2 for _ in range(N)]

for i in range(N):
    ab[i]=[int(x) for x in input().split()]

ab.sort(key=lambda j:j[1])

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

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

print(dp[N-2][T-1] + ab[-1][1])

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, t = list(map(int, readline().split()))
    ab = []
    for i in range(n):
        a, b = list(map(int, readline().split()))
        ab.append([a, b])
    ab.sort(key=lambda x: x[1], reverse=True)
    ls = [0] * t
    for i in range(1, n):
        a, b = ab[i]
        for j in range(t-a-1, -1, -1):
            ls[j+a] = max(ls[j+a], ls[j] + b)
    print(ls[-1] + ab[0][1])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,t = m()

li = [l() for i in range(n)]

ma = []
for i in range(n):
    ma.append([li[i][1],i])

ma.sort(reverse = True)

li.sort(key = lambda x:x[1],reverse = True)

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

for i in range(n):
    for k in range(li[i][0]+t-1,li[i][0]-1,-1):
        if dp[k] <= dp[k-li[i][0]] + li[i][1]:
            dp[k] = dp[k-li[i][0]] + li[i][1]


dp.sort(reverse = True)
ans = dp[0]

print(ans)

Submission status: Wrong Answer

Solution code:
N, T = map(int,input().split())
dp = [[0 for t in range(6001)] for i in range(N+1)]
for i in range(1, N+1):
  a, b = map(int,input().split())
  for t in range(6001):
    if(T > t - a >= 0 and dp[i-1][t-a] + b > dp[i-1][t]):
      dp[i][t] = dp[i-1][t-a] + b
    else:
      dp[i][t] = dp[i-1][t]
print(max(dp[N]))

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,t = m()

li = [l() for i in range(n)]

ma = []
for i in range(n):
    ma.append([li[i][1],i])

ma.sort(reverse = True)

li.sort(key = lambda x:x[1],reverse = True)

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

for i in range(n):
    for k in range(li[i][0]+t-1,li[i][0]-1,-1):
        print(k)
        if dp[k] <= dp[k-li[i][0]] + li[i][1]:
            dp[k] = dp[k-li[i][0]] + li[i][1]


dp.sort(reverse = True)
ans = dp[0]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,t = m()

li = [l() for i in range(n)]

ma = []
for i in range(n):
    ma.append([li[i][1],i])

ma.sort(reverse = True)

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

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

for i in range(n):
    for k in range(li[i][0]+t-1,li[i][0]-1,-1):
        if dp[k] <= dp[k-li[i][0]] + li[i][1]:
            dp[k] = dp[k-li[i][0]] + li[i][1]


dp.sort(reverse = True)
ans = dp[0]

print(ans)

Submission status: Wrong Answer

Solution code:
def get():
    return map(int,input().split())

N,W=get()
x=[[0,0] for _ in range(N)]
for i in range(N):
    x[i][1],x[i][0]=get()
x.sort()
w=[0]*N
v=[0]*N
for i in range(N):
    w[i], v[i] = x[i][1], x[i][0]

if W>=sum(w):
    print(sum(v))
else:
    dp=[0]*(W+1)
    for i in range(N):
        for j in range(W+w[i]-1,w[i]-1,-1):
            if j >= W:
                dp[W]=max(dp[W],dp[j-w[i]]+v[i])
            else:
                dp[j]=max(dp[j],dp[j-w[i]]+v[i])
    print(dp[W])

Submission status: Wrong Answer

Solution code:
import collections

n, t = map(int, input().split())
a = [None] * n
b = [None] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

dp = [collections.defaultdict(int) for _ in range(n + 1)]
dp[0][0] = 0
for i in sorted(range(n), key=lambda x: a[i]):
    for cur in dp[i]:
        dp[i + 1][cur] = max(dp[i + 1][cur], dp[i][cur])
        if cur < t:
            dp[i + 1][cur + a[i]] = max(dp[i + 1][cur + a[i]], dp[i][cur] + b[i])
print(max(dp[n].values()))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


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

dish = []

for _ in range(n):
    time, point = map(int, input().split())
    dish.append([time, point])

DP = [[0]*t for i in range(n+1)]
ans = defaultdict(int)

for i in range(1, n+1):
    time, point = dish[i-1]

    for j in range(t):
        DP[i][j] = max(DP[i-1][j], DP[i][j])
        if j + time >= t:
            ans[i] = max(DP[i-1][j]+point, ans[i])
            continue
        DP[i][j+time] = max((DP[i-1][j] + point), DP[i-1][j+time])

res = max(ans.values())
print(res)

Submission status: Wrong Answer

Solution code:
# 嘘解法

import sys
sys.setrecursionlimit(500000)

# 枝刈り探索（分枝限定法）
class Knapsack:
    def __init__(self, VW):
        self.VW = VW
        self.VW.sort(key=lambda vw: vw[0] / vw[1], reverse=True)
        self.n = len(VW)

    def solve(self, capacity, ok=0):
        self.ok = ok
        self.capacity = capacity
        return self._dfs(0, 0, 0)

    def _dfs(self, i, v_now, w_now):
        if i == self.n:
            self.ok = max(self.ok, v_now)
            return v_now
        ng, f = self._solve_relaxation(i, self.capacity - w_now)
        ng += v_now
        if f:
            self.ok = max(self.ok, ng)
            return ng
        if ng < self.ok:
            return -float("inf")
        res = -float("inf")
        v, w = self.VW[i]
        if w_now + w <= self.capacity:
            res = max(res, self._dfs(i + 1, v_now + v, w_now + w))
        res = max(res, self._dfs(i + 1, v_now, w_now))
        return res

    def _solve_relaxation(self, i, capacity):
        res = 0
        f = True
        for v, w in self.VW[i:]:
            if capacity == 0:
                break
            if w <= capacity:
                capacity -= w
                res += v
            else:
                f = False
                res += v * (capacity / w)
                break
        return res, f


def main():
    N, T = map(int, input().split())
    VW = []
    ma = 0
    ama = -1
    for i in range(N):
        w, v = map(int, input().split())
        if ma < v:
            ma = v
            ama = i
        VW.append([v, w])
    del VW[ama]
    if N==1:
        print(ma)
        exit()
    knapsack = Knapsack(VW)
    print(knapsack.solve(T-1) + ma)


main()

Submission status: Wrong Answer

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

a = [0]*(n)
b = [0]*(n)
dp = [0]*6666



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

z = zip(a,b)
z = sorted(z,reverse=False)
#print(z)
a, b = zip(*z)

#print(a[:n])
#print(b[:n])

for i in range(0, n):
	for j in range(3000, a[i]-1, -1):
		if ((a[i] <= j) and ((j-a[i])<t)):
			dp[j] = max(dp[j], dp[j - a[i]] + b[i])

#print(dp)
print(max(dp))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]


def main():
    n, t = LI()
    a_s = []
    b_s = []
    ab = []
    for i in range(n):
        a, b = LI()
        ab.append((a, b))
        a_s.append(a)
        b_s.append(b)

    dp = [[-INF for _ in range(t+1)] for _ in range(n+1)]
    dp_s = [[set() for _ in range(t+1)] for _ in range(n+1)]
    for i in range(n):
        dp[i][0] = 0
    for i in range(n):
        for j in range(1, t+1):
            if a_s[i] <= j:
                dp[i+1][j] = max(dp[i][j - a_s[i]] + b_s[i], dp[i][j])
                if dp[i+1][j] == dp[i][j]:
                    dp_s[i+1][j] = dp_s[i][j]
                else:

                    dp_s[i+1][j] = dp_s[i][j] | {i}

            else:
                dp[i+1][j] = dp[i][j]
                dp_s[i+1][j] = dp_s[i][j]
    all_ = {i for i in range(n)}

    for i in range(t):
        remains = all_ - dp_s[-1][i]

        max_ = 0
        for j in remains:
            if max_ < b_s[j]:
                max_ = b_s[j]
        dp[-1][i] = dp[-1][i] + max_

    print(max(dp[-1]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
tmax = 6000
n, t = [ int(v) for v in input().split() ]
dish = [ [ int(v) for v in input().split() ] for i in range(n) ]
dp_list = [ 0 for i in range(tmax) ]
dp_list_2 = [ 0 for i in range(tmax) ]

for i in range(n):
    new_dp_list = [ 0 for i in range(tmax) ]
    new_dp_list_2 = [ 0 for i in range(tmax) ]
    a, b = dish[i]
    for j in range(tmax):
        if j < a:
            new_dp_list[j] = dp_list[j]
            new_dp_list_2[j] = dp_list_2[j]
        else:
            if dp_list[j] <  dp_list[j-a] + b:
                new_dp_list[j] = dp_list[j-a] + b
                new_dp_list_2[j] = max(dp_list_2[j-a], a)
            elif dp_list[j] == dp_list[j-a] + b:
                new_dp_list_2[j] = max(dp_list_2[j], a)
            else:
                new_dp_list[j] = dp_list[j]
                new_dp_list_2[j] = dp_list_2[j]
    dp_list = new_dp_list
    dp_list_2 = new_dp_list_2

ans_list = [ 0 for i in range(tmax) ]
for i in range(tmax-1,-1,-1):
    b = dp_list[i]
    a = dp_list_2[i]
    ans_list[i-a] = max(ans_list[i-a],b)

print(max(ans_list[:t]))

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a)]
c.sort()
DP=[[0 for j in range(b+1)]for i in range(a)]
for i in range(c[0][0],b+1):
  DP[0][i]+=c[0][1]
for i in range(1,a):
  for j in range(b):
    if j<c[i][0]+1:
      DP[i][j]=DP[i-1][j]
    else:
      DP[i][j]=max(DP[i-1][j-c[i][0]]+c[i][1],DP[i-1][j])
  DP[i][b]=max(DP[i-1][b-1]+c[i][1],DP[i-1][b])
print(max(DP[-1]))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]


def main():
    n, t = LI()
    a_s = []
    b_s = []
    ab = []
    for i in range(n):
        a, b = LI()
        ab.append((a, b))
        a_s.append(a)
        b_s.append(b)

    dp = [[-INF for _ in range(t+1)] for _ in range(n+1)]
    dp_s = [[set() for _ in range(t+1)] for _ in range(n+1)]
    for i in range(n):
        dp[i][0] = 0
    for i in range(n):
        for j in range(1, t+1):
            if a_s[i] <= j:
                dp[i+1][j] = max(dp[i][j - a_s[i]] + b_s[i], dp[i][j])
                if dp[i+1][j] == dp[i][j]:
                    dp_s[i+1][j] = dp_s[i][j]
                else:

                    dp_s[i+1][j] = dp_s[i][j] | {i}

            else:
                dp[i+1][j] = dp[i][j]
                dp_s[i+1][j] = dp_s[i][j]
    all_ = {i for i in range(n)}

    for i in range(t):
        remains = all_ - dp_s[-1][i]

        max_ = 0
        for j in remains:
            if max_ < b_s[j]:
                max_ = b_s[j]
        dp[-1][i] = dp[-1][i] + max_

    print(max(dp[-1]))








if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n, t = map(int, input().split())
a = []
b = []
for i in range(n):
  ai,bi = map(int, input().split())
  a.append(ai)
  b.append(bi)
f = np.zeros((t+1, n+1))
for y in range(a[0],t+1):
	f[y,1] = b[0]
for x in range(2,n+1):
  for y in range(t+1):
    if a[x-1] <= y:
      f[y,x] = max(f[y, x-1],f[y-int(a[x-1]), x-1] + int(a[x-1]))
    else:
      f[y,x] = f[y,x-1]
print(f[t,n])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]


def main():
    n, t = LI()
    a_s = []
    b_s = []
    ab = []
    for i in range(n):
        a, b = LI()
        ab.append((a, b))
        a_s.append(a)
        b_s.append(b)

    dp = [[-INF for _ in range(t+1)] for _ in range(n+1)]
    dp_s = [[set() for _ in range(t+1)] for _ in range(n+1)]
    for i in range(n):
        dp[i][0] = 0
    for i in range(n):
        for j in range(1, t+1):
            if a_s[i] <= j:
                dp[i+1][j] = max(dp[i][j - a_s[i]] + b_s[i], dp[i][j])
                if dp[i+1][j] == dp[i][j]:
                    dp_s[i+1][j] = dp_s[i][j]
                else:
                    print(i+1, j, dp[i+1][j], dp[i][j], )
                    dp_s[i+1][j] = dp_s[i][j] | {i}

            else:
                dp[i+1][j] = dp[i][j]
                dp_s[i+1][j] = dp_s[i][j]
    all_ = {i for i in range(n)}

    for i in range(t):
        remains = all_ - dp_s[-1][i]

        max_ = 0
        for j in remains:
            if max_ < b_s[j]:
                max_ = b_s[j]
        dp[-1][i] = dp[-1][i] + max_

    print(max(dp[-1]))








if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, t = list(map(int, readline().split()))

    ab = []
    mt = 0
    for i in range(n):
        a, b = list(map(int, readline().split()))
        mt = max(mt, a)
        ab.append([a, b])
    ls = [0] * (t + mt + 1)
    for a, b in ab:
        for j in range(t, -1, -1):
            ls[j + a] = max(ls[j + a], ls[j] + b)
    print(max(ls[:t+mt]))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

for i in range(N):
    d,t=map(int,input().split())
    S.append([d,t])

S.sort(key=lambda x: x[1])
dp=[[0]*(T+2) for _ in range(N+2)]



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

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

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a)]
c.sort()
DP=[[0 for j in range(b+1)]for i in range(a)]
for i in range(c[0][0],b+1):
  DP[0][i]+=c[0][1]
for i in range(1,a):
  for j in range(c[i][0],b):
    DP[i][j]=max(DP[i-1][j-c[i][0]]+c[i][1],DP[i-1][j])
  DP[i][b]=max(DP[i-1][b-1]+c[i][1],DP[i-1][b])
print(max(DP[-1]))

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq
from collections import defaultdict
N, T = map(int, input().split())

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

q = []

for i, (a,b) in enumerate(AB):
    heapq.heappush(q, (-b, a, i))

used = [False] * N

curr = 0
ans = 0

if True:

    tmp = []

    while len(q) > 0:
        mb, a, i = heapq.heappop(q)

        if curr + a >= T:
            heapq.heappush(tmp, (mb, a, i))
        else:
            ans += -1*mb
            curr +=  a


            while len(tmp) > 0:
                nmb, na, ni = heapq.heappop(tmp)
                heapq.heappush(q, (nmb, na, ni))

    
    if len(tmp) > 0:
        mb, a, i = heapq.heappop(tmp)
        ans += -1*mb
        curr +=  a
        


print(ans)

Submission status: Wrong Answer

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

AB.sort()
# N, T = 3000, 14
# AB = [(i**2, i) for i in range(N)]

# dp[i+1][j] = i番目までの料理で、j分経った時の、最高満足度
# jがT以上のときはj == T とする(T以上における差はないので)

dp = [[0 for _ in range(6010)] for _ in range(3010)]

max_num = 0
for i, (a, b) in enumerate(AB):
    # print(a, b)
    for j in range(T):
        # if j == T-1:
        #     max_num = max(
        #         max_num,
        #         dp[i][j] + b
        #     )
        if j+a < T:
            dp[i+1][j+a] = max(
                dp[i+1][j+a],
                dp[i][j] + b
            )
        else:
            dp[i+1][T] = max(
                dp[i+1][T],
                dp[i][j] + b
            )

        dp[i+1][j] = max(
            dp[i+1][j],
            dp[i][j]
        )

# for dp_i in dp:
#     print(dp_i)

print(max_num)