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: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



@mt
def slv(N, T, AB):
    AB.sort(key=lambda x: x[0])

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

    for t in range(T):
        for i in range(len(AB)):
            a, b = AB[i]
            if t >= a:
                dp[t][i] = max(dp[t-a][i-1] + b, dp[t-1][i], dp[t][i-1])
            else:
                dp[t][i] = max(dp[t-1][i], dp[t][i-1])

    B = list(map(lambda x: x[1], AB))
    B.append(0)
    
    dp = dp[-1]
    dp.pop()
    ans = 0
    for i, v in enumerate(dp):
        ans = max(ans, v + max(B[i+1:]))
    return ans


def main():
    N, T = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, T, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():

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

    dp = [[0, set()] for _ in range(T)]
    ans = 0
    for i in range(T):
        for j in range(N):
            if j not in dp[i][1]:
                k = i+C[j][1]
                if k > T-1:
                    ans = max(ans, dp[i][0] + C[j][0])
                else:
                    if dp[i][0]+C[j][0] > dp[k][0]:
                        dp[k][0] = dp[i][0]+C[j][0]
                        dp[k][1] = dp[i][1] | {j}
        ans = max(ans, dp[i][0])

    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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]:
      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: Accepted

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

dp = [-1] * 6001
dp[0] = 0
for a, b in sorted(X):
    for j in reversed(range(T)):
        if dp[j] == -1:
            continue

        dp[j + a] = max(dp[j + a], dp[j] + b)
            
print(max(dp))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def knapsack(N,W,weight,value):
  dp=[[float('inf') for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1):
    dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
        else:
          dp[i+1][w]=dp[i][w]
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
dp=knapsack(n,t-1,a,b)
ans=[]
for i in range(n):
  if i!=n:
    ans.append(dp[i][t-1]+b[i])
  else:
    ans.append(dp[n][t])
print(max(ans))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
        else:
          dp[i+1][w]=dp[i][w]
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
dp=knapsack(n,t-1,a,b)
ans=[]
for i in range(n):
  if i!=n:
    ans.append(dp[i][t-1]+b[i])
  else:
    ans.append(dp[n][t])
print(max(ans))

Submission status: Accepted

Solution code:
import sys
def LI(): return map(int,sys.stdin.readline().split())

def main():
    N,T = LI()
    AB = []
    for i in range(N):
        A,B = LI()
        AB.append([A,B])

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

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

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

    ans = 0
    for i in range(T+1):
        ans = max(dp[N][i],ans)
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

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

dp = [[0] * (T + 1) for _ in range(N + 1)]
for i, (a, b) in enumerate(sorted(X)):
    for j in range(T + 1):
        if j == T:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - 1] + b)
        elif j < a:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - a] + b)
            
print(dp[-1][-1])

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
        else:
          dp[i+1][w]=dp[i][w]
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
dp=knapsack(n,t-1,a,b)
ans=[]
for i in range(n):
  if i!=n:
    ans.append(dp[i][t-1]+b[i])
  else:
    ans.append(dp[n][t-i])
print(max(ans))

Submission status: Accepted

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
            )
        dp[i+1][j] = max(
            dp[i+1][j],
            dp[i][j]
        )
        dp[i+1][j+a] = max(
            dp[i+1][j+a],
            dp[i][j] + b
        )

# for dp_i in dp:
#     print(dp_i)

print(max_num)

Submission status: Accepted

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

def main():
    n,t=map(int,input().split())
    AB=[list(map(int,input().split())) for _ in range(n)]
    AB.sort()
    DP=[[0]*(6001) for _ in range(n+1)]
    for i,(a,b) in enumerate(AB):
        for j in range(1,6001):
            if j<a:
                DP[i+1][j]=max(DP[i][j],DP[i+1][j-1])
            elif j-a<t:
                DP[i+1][j]=max(DP[i][j],DP[i+1][j-1],DP[i][j-a]+b)
            else:
                DP[i+1][j]=max(DP[i][j],DP[i+1][j-1])
    print(max(DP[-1]))
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, T = I[:2]
A, B = I[2::2], I[3::2]
dp = [-1] * 6001
dp[0] = 0
for a, b in sorted(zip(A, B)):
    for k in range(T - 1, -1, -1):
        if dp[k] == -1:
            continue
        dp[k + a] = max(dp[k + a], dp[k] + b)
print(max(dp))

Submission status: Accepted

Solution code:
import math

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)

    # divisors.sort()
    return divisors

#a = list(map(int, input().split()))

n,T = list(map(int, input().split()))
item=[]

for i in range(n):
    item.append(list(map(int, input().split())))
    
dp = [[-1 for i in range(T+1)] for j in range(n+1)]

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

item.sort(key=lambda x:x[0])
    
for i in range(n):
    nowit=item[i]
    for j in range(T):
        z = dp[i][j]
        y = dp[i+1][min(j+nowit[0],T)]
        down = dp[i+1][j]
        dp[i+1][j] = max(dp[i][j],down)
        if(z >= 0):
            dp[i+1][min(j+nowit[0],T)] = max(z+nowit[1],y)
    dp[i+1][T] = max(dp[i][T],dp[i+1][T])
            
print(max(dp[n]))

#for i in range(len(dp)):
    #print(dp[i])

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter


def main():
    input = sys.stdin.readline
    N, T = map(int, input().strip().split())
    foods = sorted([list(map(int, input().strip().split())) for _ in range(N)], key=itemgetter(0))

    ans = 0
    dp = [[0] * (T+1) for _ in range(N+1)]
    for j, food in enumerate(foods):
        n_a, n_b = food
        for k in range(T+1):
            if k == T:
                dp[j+1][k] = max(dp[j][k], dp[j][k-1]+n_b)
            elif k < n_a:
                dp[j+1][k] = dp[j][k]
            else:
                dp[j+1][k] = max(dp[j][k], dp[j][k-n_a]+n_b)
        #print(dp[j+1])
    ans = dp[-1][-1]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, T = I[:2]
A, B = I[2::2], I[3::2]
dp = [-1] * 6001
dp[0] = 0
for a, b in sorted(zip(A, B)):
    dp_new = dp[:]
    for k in range(T):
        if dp[k] == -1:
            continue
        dp_new[k + a] = max(dp[k + a], dp[k] + b)
    dp = dp_new
print(max(dp))

Submission status: Accepted

Solution code:
# E
import numpy as np
N, T = map(int, input().split())
# A=cost. B=value
A, B = np.array([input().split() for _ in range(N)], dtype=int).T

weight,value = A, B
# dp[i][w] = i番目までからwを超えないように選んだ時の最大値, まだ最後の食べ物を選んでない
d0 = np.zeros((N,T),int)
# dp[i][w] = i番目までからwを超えないように選んだ時の最大値, もう最後の食べ物を選んだ
d1 = np.zeros((N,T),int)
# 初期値として0番目の商品を加える
d0[0,weight[0]:] = value[0]
d1[0,:] = value[0]

for n in range(1, N):
  w = weight[n]
  # w < weight[n]
  d0[n][:w] = d0[n-1][:w]
  d1[n][:w] = np.fmax(d1[n-1][:w], d0[n-1][:w] + value[n])
  # w >= weight[n]
  d0[n][w:] = np.fmax(d0[n-1][:-w] + value[n], d0[n-1][w:])
  d1[n][w:] = np.fmax(np.fmax(d1[n-1][:-w] + value[n], d1[n-1][w:]), d0[n-1][w:] + value[n])

print(d1[-1,-1])

Submission status: Accepted

Solution code:
n, t = [int(i) for i in input().split()]
ab = []
for _ in range(n):
    ab.append([int(i) for i in input().split()])
ab.sort(key=lambda x:x[0])
aa = t+max([i[0] for i in ab])+1
c = [0] * aa
for i in ab:
    d = c[:]
    for j in range(t):
        k = d[j]
        l = i[0] + j
        if l >= aa:
            continue
        c[l] = max(c[l], d[j] + i[1])
print(max(c))

Submission status: Accepted

Solution code:
def examE():
    N, T = LI()
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = LI()
    dp = [[0 for _ in range(T+ 1)] for _ in range(N + 1)]
    dp2 = [[0 for _ in range(T+ 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(A[i],T+1):
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - A[i]] + B[i])
            dp2[i + 1][j] = max(dp2[i + 1][j], dp2[i][j - A[i]] + B[i])
        for j in range(1,T+1):
            dp2[i+1][j] = max(dp2[i+1][j], dp[i][j-1] + B[i], dp2[i][j])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
#    print(dp[N][T])
    ans = dp2[N][T]
    print(ans)

import sys,copy,bisect,itertools
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE()

Submission status: Accepted

Solution code:
# Python3 TLE, PyPy3 AC

import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, t = ril()
ls = rils(n)

dp = [[0] * t for _ in range(n + 1)]
for i in range(n + 1):
    for t0 in range(t):
        a, b = ls[i - 1]
        if i == 0 or t0 == 0:
            continue
        elif a <= t0:
            dp[i][t0] = max(dp[i - 1][t0], dp[i - 1][t0 - a] + b)
        else:
            dp[i][t0] = dp[i - 1][t0]

res = set()
val = dp[n][t - 1]
t0 = t - 1
for i in reversed(range(n)):
    a, b = ls[i]
    if val <= 0:
        break
    if val == dp[i][t0]:
        continue
    else:
        res.add(i)
        val -= b
        t0 -= a

m = 0
for i, (_, v) in enumerate(ls):
    if i not in res:
        m = max(m, v)
print(dp[n][t - 1] + m)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,t = LI()
    g = LIR(n)
    g.sort()
    dp = [0]*(t+3001)
    ans = 0
    for i in range(n):
        w,v = g[i]
        for j in range(w,t+3001)[::-1]:
            nd = dp[j-w]+v
            if j-w < t:
                if ans < nd:
                    ans = nd
            if dp[j] < nd:
                dp[j] = nd
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,t = map(int,input().split())
arr = []
for i in range(n):
    arr.append(list(map(int,input().split())))
arr.sort(key = lambda x:x[0])
dp = [[0]*(t+1) for _ in range(n + 1)]
for i in range(n):
    for j in range(t + 1):
        if j > 0:
            if j - arr[i][0] > 0.5: dp[i + 1][j-arr[i][0]] = max(dp[i + 1][j-arr[i][0]],dp[i][j] + arr[i][1])
            else:
                dp[i + 1][0] = max(dp[i + 1][0],dp[i][j] + arr[i][1])
        dp[i + 1][j] = max(dp[i + 1][j],dp[i][j])
print(max(dp[n]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0

n,t=map(int,input().split())
t-=1
AB=[list(map(int,input().split())) for i in range(n)]
AB.sort(key=lambda tup:tup[1])
dp = [[0]*(t+1) for i in range(n+1)]
prev = [[0]*(t+1) for i in range(n+1)]

for i in range(1, n+1):
    for j in range(0, t+1):
        if j < AB[i-1][0]:
            dp[i][j] = dp[i-1][j]
            prev[i][j] = j
            # prev[i][j] = j - AB[i-1][0]
        else:
            if dp[i-1][j] > dp[i-1][j-AB[i-1][0]]+AB[i-1][1]:
                dp[i][j] = dp[i-1][j]
                prev[i][j] = j
            else:
                dp[i][j] = dp[i-1][j-AB[i-1][0]]+AB[i-1][1]
                prev[i][j] = j - AB[i-1][0]
S=set()
cur=t
for i in range(n-1,-1,-1):
    if (prev[i+1][cur] == cur - AB[i][0]):
        S.add(i)
    cur=prev[i+1][cur]

tmp=0
for i in range(n):
    if i not in S:
        tmp=max(tmp,AB[i][1])
    


# int cur_w = W;
# for (int i=n-1; i >= 0; --i) {
#     // 選んでいた場合
#     if (prev_w[i+1][cur_w] == cur_w - weight[i]) {
#         cout << i << " th item (weight = " << weight[i] << ", value = " << value[i] << ")" << endl;}

#     // 復元テーブルをたどる
#     cur_w = prev_w[i+1][cur_w];

print(dp[n][t]+tmp)
# print(dp[n][t],tmp)
# print(S)
# for di in dp:
#     print(di)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N, T = map(int, readline().split())
AB = [list(map(int, readline().split())) for _ in range(N)]
AB.sort()
A, B = map(list, zip(*AB))
dp = [0]*(T + max(A) + 2)
L = len(dp)
for i in range(N):
    dp2 = dp[:]
    a, b = A[i], B[i]
    for t in range(L):
        if T + a > t >= a:
            dp2[t] = max(dp2[t], dp[t-a] + b)
    dp = dp2[:]
print(max(dp))

Submission status: Accepted

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

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

M = [0] * N
for i in range(N - 1, -1, -1) :
    M[i] = max(M[i], vw[i][1])
        
dp = [-float('inf')] * T
dp[0] = 0
ret = 0

for n, (w, v) in enumerate(vw) :
    for i in range(T-1, w-1, -1) :
        dp[i] = max(dp[i], dp[i-w]+v)
    
    if n + 1 < N :
        ret = max(ret, max(dp) + M[n + 1])
    else :
        ret = max(ret, max(dp))
    
print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, T = map(int, input().split())
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())

    u = [0] + [B[0]] * (T)
    v = [0] * A[0] + [B[0]] * (T - A[0] + 1)
    
    for i in range(1, N):
        a, b = A[i], B[i]
        for t in range(T, 0, -1):
            vv = b + v[t - 1]
            if t >= a:
                vv = max(vv, b + u[t - a])
            if u[t] < vv:
                u[t] = vv
        for t in range(T, a - 1, -1):
            vv = b + v[t - a]
            if v[t] < vv:
                v[t] = vv
    print(u[T])

            



main()

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 


#x,y = [int(i) for i in readline().split()]
#n = int(input())

n,t = [int(i) for i in readline().split()]
ab = [[int(i) for i in readline().split()] for i in range(n)]

from operator import itemgetter


ab.sort(key = itemgetter(1), reverse = True)
ab.sort(key = itemgetter(0))

dp = [0]*(t)
val = 0

#print(ab)

for a,b in ab:
    for i in range(max(0,t-a),t):
        val = max(val,dp[i]+b)
    
    for i in range(t-1,-1,-1):
        if i-a >= 0:
            if dp[i-a] != 0 or i==a:
                dp[i] = max(dp[i], dp[i-a] + b)
        else:
            break
    #print(dp,val)

print(max(max(dp),val))

Submission status: Accepted

Solution code:
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)

dp = [[0 for j in range(t+1)] for i in range(n+1)]
prev = [[(0, 0) for j in range(t+1)] for i in range(n+1)]

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

happy = dp[n][t-1]
i = n
j = t-1


used = set([])
while i > 0 or j > 0:
    pi, pj = prev[i][j]
    if dp[pi][pj] != dp[i][j]:
        used.add(pi)
    i = pi
    j = pj

unused = []
for i in range(n):
    if i not in used:
        unused.append(b[i])

if len(unused) == 0:
    ans = happy
else:
    ans = happy + max(unused)

print(ans)

Submission status: Accepted

Solution code:
N, W = map(int,input().split())
v = [0] * N
w = [0] * N
prev_w = [[0 for i in range(W + 1)] for j in range(N + 1)]
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

for i in range(N):
    w[i], v[i] = map(int,input().split())

for i in range(N):
    for j in range(W + 1):
        if j >= w[i]:
            if dp[i+1][j] < dp[i][j-w[i]] + v[i]:
                dp[i+1][j] = dp[i][j-w[i]] + v[i]
                prev_w[i+1][j] = j - w[i]
        if dp[i+1][j] < dp[i][j]:
            dp[i+1][j] = dp[i][j]
            prev_w[i+1][j] = j

ans=dp[-1][-1]

sel=set()
cur_w = W-1
i=N-1
while i>=0:
    if (prev_w[i+1][cur_w] == cur_w - w[i]) :
        sel.add(i)
    cur_w = prev_w[i+1][cur_w]
    i-=1

tmp=0
for i in range(N):
    if i not in sel:
        tmp=max(v[i],tmp)
print(max(ans,dp[-1][-2]+tmp))

Submission status: Accepted

Solution code:
# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W
# ty geekforgeeks
def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 
  
    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(W+1):
            if i==0 or w==0: 
                K[i][w] = 0
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 
        res = K[n][W] 
      
    w = W
    used = [False for i in range(N)]
    for i in range(n, 0, -1): 
        if res <= 0: 
            break
        # either the result comes from the 
        # top (K[i-1][w]) or from (val[i-1] 
        # + K[i-1] [w-wt[i-1]]) as in Knapsack 
        # table. If it comes from the latter 
        # one/ it means the item is included. 
        if res == K[i - 1][w]: 
            continue
        else: 
            # This item is included. 
            used[i - 1] = True
              
            # Since this weight is included 
            # its value is deducted 
            res = res - val[i - 1] 
            w = w - wt[i - 1] 
    return K[n][W], used

N, T = map(int, input().split())
wts = [None for i in range(N)]
val = [None for i in range(N)]
for i in range(N):
    a, b = map(int, input().split())
    wts[i] = a
    val[i] = b

best, _ = knapSack(T, wts, val, N)
other, used = knapSack(T - 1, wts, val, N)
add = 0
for i, wasUsed in enumerate(used):
    if not wasUsed: add = max(add, val[i])
print(max(best, other + add))

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
food = list(list(map(int,input().split()))for i in range(N))
DP = [[0]*(T) for i in range(N+1)]
for i in range(N):
    a,b = food[i]
    for j in range(min(a,T)):
        DP[i+1][j] = DP[i][j]
    for j in range(a,T):
        DP[i+1][j] = max(DP[i][j],DP[i][j-a]+b)
ans = 0
i = N
j = T-1
while i > 0 and j > 0:
    if DP[i][j] == DP[i][j-1]:
        j -= 1
    elif DP[i][j] == DP[i-1][j]:
        i -= 1
    else:
        food[i-1][1] = 0
        j -= food[i-1][0]
        i -= 1
food.sort(reverse=True,key= lambda x:x[1])
print(DP[-1][-1]+food[0][1])

Submission status: Accepted

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

max_a = 0
for i in range(len(ab)):
    max_a = max(max_a, ab[i][0])

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

# use as the last
dp = [[0] * (t + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(t + 1):
        a = ab[i][0]
        b = ab[i][1]
        if j < a:
            if j >= 1:
                dp[i+1][j] = max(dp[i][j], dp2[i][j-1] + b)
            else:
                dp[i+1][j] = dp[i][j]
        else:
            if j >= 1:
                dp[i+1][j] = max(dp[i][j], dp[i][j - a] + b, dp2[i][j-1] + b)
            else:
                dp[i+1][j] = max(dp[i][j], dp[i][j - a] + b)

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,t=map(int,input().split())
AB=[]
for i in range(n):
  a,b=map(int,input().split())
  AB.append((a,b))
AB.sort(key=lambda x:x[0])
ans=0
dp=[[0]*(t) for _ in range(n+1)]
for i in range(n-1):
  a,b=AB[i]
  for j in range(t):
    if j>=a:
      dp[i+1][j]=max(dp[i][j-a]+b,dp[i][j],dp[i+1][j-1])
    else:
      dp[i+1][j]=max(dp[i][j],dp[i+1][j-1])
  ans=max(ans,dp[i+1][t-1]+AB[i+1][1])

print(ans)

Submission status: Accepted

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

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

dp = [[0 for _ in range(N+1)] for _ in range(T+1)]
# 重さwまで品物nまででで最大になる価値

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

for n in range(N): # 品物nまでの世界で決めていく
    a, b = AB[n]
    for w in range(T):
        if a > w: # カバンに入りきらないなら入れられない
            dp[w][n+1] = dp[w][n]
            prev[w][n+1] = w
        else: #カバンに入れられる可能性があるなら
            if b+dp[w-a][n] >= dp[w][n]:
                dp[w][n+1] = dp[w-a][n] + b
                prev[w][n+1] = w - a
            else:
                dp[w][n+1] = dp[w][n]
                prev[w][n+1] = w

ans = dp[T-1][N]
used = [False]*N
c = T-1
for i in reversed(range(N)):
    if prev[c][i+1] == c - AB[i][0]:
        used[i] = True
    c = prev[c][i+1]

p = 0
for i in range(N):
    if not used[i] and AB[i][1] > p:
        p = AB[i][1]

print(ans+p)

Submission status: Accepted

Solution code:
_, t, *L = map(int, open(0).read().split())
d = [0] * (t + max(L[::2]))
for w, v in sorted((x, y) for x, y in zip(*[iter(L)] * 2)):
	for i in range(t + w - 1, w - 1, -1):
		if d[i - w] + v > d[i]:
			d[i] = d[i - w] + v
print(max(d))

Submission status: Accepted

Solution code:
#import numpy as np

def knapsack2(N,W,weight,value,WW):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(WW)] for j in range(N+1)]
  for i in range(WW):
      dp[0][i]=0
  maxval = 0
  #DP
  for i in range(N):
    for w in range(WW):
      if weight[i]<=w:
        if w-weight[i]>=W: #時間切れ
          dp[i+1][w]=dp[i][w]
        else: #注文可能
          dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: #NG
        dp[i+1][w]=dp[i][w]
    maxval = max([maxval, max(dp[i+1])])
#  for elem in dp:
#    print(elem[:2*W])
  return maxval
  #return np.max(np.array(dp))
  #return dp[N][2*W]

N, T = map(int,input().split())
WW = T+3000
ab = []
for i in range(N):
    ab.append(tuple(map(int,input().split())))

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

weight = [elem[0] for elem in ab]
value = [elem[1] for elem in ab]
res = knapsack2(N,T,weight,value,WW)
print(res)

Submission status: Accepted

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


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

Submission status: Accepted

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

dp1 = [[0]*T for i in range(N+1)]
for n in range(N):
    for w in range(T):
        if w-AB[n][0]>=0:
            dp1[n+1][w] = max(dp1[n][w],dp1[n][w-AB[n][0]]+AB[n][1])
        else:
            dp1[n+1][w] = dp1[n][w]

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

dp2 = [[0]*T for i in range(N+1)]
for n in range(N):
    for w in range(T):
        if w-AB[-n-1][0]>=0:
            dp2[n+1][w] = max(dp2[n][w],dp2[n][w-AB[-n-1][0]]+AB[-n-1][1])
        else:
            dp2[n+1][w] = dp2[n][w]

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

ans = 0
for n in range(N):
    for w in range(T):
        ans = max(AB[n][1]+dp1[n][w]+dp2[N-n-1][T-1-w],ans)

print(ans)

Submission status: Accepted

Solution code:
n,t = map(int,input().split())
menu = []
time = [] #(time,value)
value = []

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

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

for i in range(n):
    time.append(menu[i][0])
    value.append(menu[i][1])

dp = [[0 for _ in range(t+1)] for __ in range(n+1)]
ind = [[-1 for _ in range(t+1)] for __ in range(n+1)]

#dp[i+1][w]: i番目までを使う、時間w超えない

for i in range(n):
    for w in range(t+1):
        if time[i] < w:
            if dp[i][w-time[i]]+value[i] > dp[i][w]:
                dp[i+1][w] = dp[i][w-time[i]]+value[i]
                ind[i+1][w] = ind[i][w-time[i]]
            else:
                dp[i+1][w] = dp[i][w]
                ind[i+1][w] = i
        else:
            dp[i+1][w] = dp[i][w]
            ind[i+1][w] = i

if ind[n][t] < 0:
    print(dp[n][t])
else:
    print(dp[n][t]+value[ind[n][t]])