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

Solution (Python):
import sys
from collections import defaultdict

n, t = map(int, input().split())
knapsack = defaultdict(lambda: 0)
knapsack[0] = 0
tmp_ans = 0
cuisines = [tuple(map(int, line.split())) for line in sys.stdin]
cuisines.sort()
for a, b in cuisines:
    for time, satisfied in list(knapsack.items()):
        if time + a >= t:
            tmp_ans = max(tmp_ans, satisfied + b)
            continue
        knapsack[time + a] = max(knapsack[time + a], satisfied + b)

print(max(tmp_ans, max(knapsack.values())))

Solution (Python):
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)]
  dp2=[[0 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]
          dp2[i+1][w]=w-weight[i]
        else:
          dp[i+1][w]=dp[i][w]
          dp2[i+1][w]=w
        
      else:
        dp[i+1][w]=dp[i][w]
        dp2[i+1][w]=w
  
  l=[]
  x=W
  for i in range(n-1,-1,-1):
    if dp2[i+1][x]==x-weight[i]:
      l.append(i)
    x=dp2[i+1][x]
  return dp[N][W],l
 
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
z=knapsack(n,t-1,a,b)
L=[0]*n
for i in range(len(z[1])):
  L[z[1][i]]=1
M=[]
for i in range(n):
  if L[i]==0:
    M.append(l[i][1])
if len(M)==0:
  print(z[0])
else:
  print(z[0]+max(M))

Solution (Python):

import sys


def solve(N: int, T: int, A: "List[int]", B: "List[int]"):
    

    AB = list(zip(A,B))
    AB.sort(key=lambda x:x[0])
    A = [AB[i][0] for i in range(N)]
    B = [AB[i][1] for i in range(N)]

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

        for j in range(0,T):

            if j >= A[i]: 
                dp[i+1][j] = max(dp[i][j-A[i]]+B[i],dp[i][j])
            else: 
                dp[i+1][j] = dp[i][j]
             
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    T = int(next(tokens))  
    A = [int()] * (N)  
    B = [int()] * (N)  
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, T, A, B)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
N, T = map(int, input().split())
D = []
for _ in range(N):
    a, b = map(int, input().split())
    D.append((a,-b))

D.sort()

dp = [[0] * (T) for _ in range(N)]
for i in range(1, N):
    a, b = D[i-1]
    b = -b
    for t in range(T):
        dp[i][t] = dp[i-1][t]
        if t >= a:
            dp[i][t] = max(dp[i][t], dp[i-1][t-a]+b)

print(max(-D[i][1] + dp[i][-1] for i in range(1,N)))

Solution (Python):
import sys
import numpy as np
read = sys.stdin.read

N, T, *AB = map(int, read().split())
AB = np.array(AB).reshape(N, 2)
AB = AB[np.argsort(AB[:, 0], axis=0)]

dp = np.zeros(T, np.int64)
answer = []

for a, b in AB:
    answer.append(dp[-1] + b)
    if a > T:
        continue

    dp[a:] = np.maximum(dp[:T - a] + b, dp[a:])

print(max(answer))

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,T=map(int,input().split())
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    AB.sort()

    dp=[0]*T
    ans=-INF
    for i in range(n):
        a,b=AB[i]
        ndp=dp[:]
        for t in range(T):
            if(t+a<T):
                ndp[t+a]=max(ndp[t+a],dp[t]+b)
            else:
                ans=max(ans,dp[t]+b)
        dp=ndp
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,T=map(int,input().split())
    AB=[tuple(map(int,input().split())) for _ in range(n)]
    AB.sort()

    dp=[0]*T
    ans=-INF
    for i in range(n):
        a,b=AB[i]
        ndp=dp[:]
        for t in range(T):
            if(t+a<T):
                ndp[t+a]=max(ndp[t+a],dp[t]+b)
            else:
                ans=max(ans,dp[t]+b)
        dp=ndp
    print(max(ans,max(dp)))
resolve()

Solution (Python):
import sys
import numpy as np
read = sys.stdin.read

N, T, *AB = map(int, read().split())
AB = np.array(AB).reshape(N, 2)
AB = AB[np.argsort(AB[:, 0], axis=0)]

dp = np.zeros(T, np.int64)
answer = []

for a, b in AB:
    answer.append(dp[-1] + b)
    if a > T:
        continue

    dp[a:] = np.maximum(dp[:T - a] + b, dp[a:])

answer.append(dp.max())
print(max(answer))

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

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

print(ans)

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

Solution (Python):
import collections

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

dp = [[0] * (t + 1) for _ 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])
        k = min(t, j + a[i])
        dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + b[i])
print(max(map(max, dp)))

Solution (Python):
n, t = [int(_) for _ in input().split()]

ab = []

for i in range(n):
    ab_ = [int(_) for _ in input().split()]
    ab.append(ab_)

ab.sort()

dp = [-1 for _ in range(6000)]
dp[0] = 0
dp2 = dp[:]


dplist = [0]

for i in range(n):

    dp_trans = ab[i][0]
    dp_delicious = ab[i][1]

    for j in range(t):
        if dp[j] != -1:
            dp2[j+dp_trans] = max(dp[j+dp_trans], dp[j] + dp_delicious)
    dp = dp2[:]

print(max(dp))

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,w = inpl()
wv = [inpl() for i in range(n)]
dp = [[0 for i in range(w+1)] for j in range(n+1)]
wv.sort()
wv.sort(key=lambda x:x[1])
ww = [0] * n
vv = [0] * n
for i in range(n):
    ww[i],vv[i] = wv[i][0], wv[i][1]
for i in range(n-1):
    for j in range(w+1):
        if j >= ww[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-ww[i]]+vv[i])
        else:
            dp[i+1][j] = dp[i][j]
res = dp[n-1][w-1]+wv[n-1][1]

dp = [[0 for i in range(w+1)] for j in range(n+1)]
ww[-1],ww[-2] = ww[-2],ww[-1]
vv[-1],vv[-2] = vv[-2],vv[-1]
for i in range(n-1):
    for j in range(w+1):
        if j >= ww[i]:
            dp[i+1][j] = max(dp[i][j], dp[i][j-ww[i]]+vv[i])
        else:
            dp[i+1][j] = dp[i][j]
print(max(res,dp[n-1][w-1]+vv[n-1]))

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    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): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    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[0])

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)

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

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

a = []
b = []
for ai, bi in ab:
    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)

Solution (Python):
N, T = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()
INF = float('inf')

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

for a, b in AB:
    for t in range(T)[:: -1]:
        dp[min(T, t + a)] = max(dp[min(T, t + a)], dp[t] + b)

print(max(dp))

Solution (Python):
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

n,t = MAP()
dp = [0] * 6005
ab = []
for i in range(n):
    ab.append(MAP())

ab.sort(key=lambda x: x[0])
for u in ab:
    for i in range(6004-u[0], -1, -1):
        if i < t:
            dp[i+u[0]] = max(dp[i+u[0]], dp[i] + u[1])
print(max(dp))

Solution (Python):
import sys
input=sys.stdin.readline
n,t=map(int,input().split())
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
dp=[[0]*t for i in range(n+1)]
check=[[0]*t for i in range(n+1)]
for i in range(n):
    for j in range(t):
        if j>=l[i][0]:
            if dp[i+1][j]<dp[i][j]:
                dp[i+1][j]=dp[i][j]
            if dp[i+1][j-l[i][0]]<dp[i][j]+l[i][1]:
                dp[i+1][j-l[i][0]]=dp[i][j]+l[i][1]
                check[i+1][j-l[i][0]]=j
        else:
            if dp[i+1][j]<dp[i][j]:
                dp[i+1][j]=dp[i][j]
M=0
for j in range(t):
    M=max(M,dp[n][j])
m0=0
for j in range(t):
    if dp[n][j]==M:
        x=j
        g=[]
        for i in range(n,0,-1):
            if check[i][x]:
                x=check[i][x]
            else:
                g.append(i-1)
        m=0
        for i in g:
            m=max(m,l[i][1])
        m0=max(m0,m)
print(M+m0)

Solution (Python):

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

Solution (Python):
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())

Solution (Python):
import sys
input=sys.stdin.readline
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))

Solution (Python):
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])

dish.sort()
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)

Solution (Python):
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]))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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())

Solution (Python):
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])

Solution (Python):
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))

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

AB.sort()






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

max_num = 0
for i, (a, b) in enumerate(AB):
    
    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
        )




print(max_num)

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N, T = map(int, input().split())
    food = [[int(i) for i in input().split()] for _ in range(N)]
    food.sort()
    DP = [[0 for _ in range(T)] for i in range(N + 1)]
    for i in range(N):
        a, b = food[i]
        for t in range(T):
            DP[i+1][t] = max(DP[i][t], DP[i+1][t])
            if t+a < T: DP[i+1][t+a] = max(DP[i+1][t+a], DP[i][t] + b)
    max_dish = 0
    for i in range(N):
        max_dish = max(max_dish, max(DP[i]) + food[i][1])
    print(max_dish)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):
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)

    
    return divisors



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

Solution (Python):
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)
        
    ans = dp[-1][-1]
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
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))

Solution (Python):

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

A, B = np.array([input().split() for _ in range(N)], dtype=int).T

weight,value = A, B

d0 = np.zeros((N,T),int)

d1 = np.zeros((N,T),int)

d0[0,weight[0]:] = value[0]
d1[0,:] = value[0]

for n in range(1, 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])
  
  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])

Solution (Python):
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))

Solution (Python):
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])

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

Solution (Python):


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)

Solution (Python):

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


if __name__ == "__main__":
    solve()

Solution (Python):
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

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

Solution (Python):
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]))