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:
N,T = map(int,input().split())
foods = []
for _ in range(N):
  a,b = map(int,input().split())
  foods.append([a,b])

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

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

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

# for d in dp:
#   print(d)

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

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

Submission status: Accepted

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

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

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

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

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

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

print(ndp2[-1])

Submission status: Accepted

Solution code:

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

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

for i in range(N):
    for j in range(T + 1):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        if dp[i][j] >= 0 and j < T:
            dp[i + 1][min(T, j + X[i][0])] = max(dp[i + 1][min(T, j + X[i][0])],
                                                 dp[i][j] + X[i][1])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros((N+1, 2, T), np.int64)
for i, (A, B) in enumerate(ABs):
    dp[i+1] = dp[i]
    dp[i+1, 1] = np.maximum(dp[i, 0] + B, dp[i+1, 1])
    dp[i+1, :, A:] = np.maximum(dp[i, :, :-A] + B, dp[i+1, :, A:])

print(np.max(dp[N]))

Submission status: Accepted

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

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

import sys
input = sys.stdin.readline


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

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


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

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

max_weight = max(weight_list)

W = T + max_weight - 1

print(knapsack_weight(single=True))

Submission status: Accepted

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

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

import sys
input = sys.stdin.readline

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, t = ns()
    d = [na() for _ in range(n)]
    d.sort()

    dp = [-1 for _ in range(t + 3000 + 1)]
    dp[0] = 0

    for a, b in d:
        for i in range(t - 1, -1, -1):
            if dp[i] >= 0:
                dp[i + a] = max(dp[i + a], dp[i] + b)

    print(max(dp))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# n<3000, t<3000, a,b <3000
import sys

input = sys.stdin.buffer.readline

n, t = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
rAB = AB[::-1]
dp1 = [[0] * (t + 1) for _ in range(n + 1)]
dp2 = [[0] * (t + 1) for _ in range(n + 1)]

for i in range(n):
    ni = i + 1
    a, b = AB[i]
    for j in range(t + 1):
        nj = j + a
        if nj <= t:
            dp1[ni][nj] = max(dp1[i][j] + b, dp1[ni][nj])
        dp1[ni][j] = max(dp1[ni][j], dp1[i][j])
    c, d = rAB[i]
    for j in range(t + 1):
        nj = j + c
        if nj <= t:
            dp2[ni][nj] = max(dp2[i][j] + d, dp2[ni][nj])
        dp2[ni][j] = max(dp2[ni][j], dp2[i][j])

ans = 0
# i-1まで→先頭i個
# 後ろはn-(i+1)個
for i in range(n):
    for j in range(t):
        temp = AB[i][1]
        if i >= 1:
            temp += dp1[i][j]
        if n - i - 1 >= 1:
            temp += dp2[n - i - 1][t - 1 - j]
        ans = max(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N, T = list(map(int, input().split()))
    AB = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[0])
    dp = [[0 for _ in range(T)] for __ in range(N)]
    for i in range(1, N):
        time, value = AB[i-1]
        for j in range(T-1, -1, -1):
            dp[i][j] = dp[i-1][j]
            if j >= time:
                dp[i][j] = max(dp[i][j], dp[i-1][j-time]+value)
    print(max(dp[i][T-1]+AB[i][1] for i in range(N)))
    
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N,T=map(int,input().split())
A=[]
for i in range(N):
  a,b=map(int,input().split())
  A.append((a,b))
A=sorted(A)
dp=[[0]*(T) for j in range(N)]
#print(A)

for i in range(N):
  for j in range(T):
    if j>=A[i][0]:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-A[i][0]]+A[i][1])
    else:
      dp[i][j]=dp[i-1][j]
#print(dp)
bma=[0]
t=0
for i in range(N-1,0,-1):
  t=max(t,A[i][1])
  bma=[t]+bma
#print(bma)
ans=0
for i in range(N):
  d=dp[i][-1]+bma[i]
  ans=max(d,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    N,T = LMIIS()
    AB = []
    for i in range(N):
        AB.append(LMIIS())
    
    AB.sort()
    dp = [-1] * (T+3000)
    dp[0] = 0
    for a,b in AB:
        tmpdp = dp[:]
        for j in range(T):
            if dp[j] != -1:
                tmpdp[j+a] = max(dp[j+a],dp[j]+b)
        dp = tmpdp
    print(max(dp))






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

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

N, A = getNM()
w = []
v = []
for i in range(N):
    a, b = getNM()
    w.append(a)
    v.append(b)

# limit回までコストカットできる
def knapsack_6(N, upper, limit, weight, value):
    dp = [[[0] * (upper + 1) for i in range(limit + 1)] for j in range(N + 1)]

    for i in range(N):
        # ボーナスでコスト１にするのを使ったか 使うと-1する
        for j in range(limit + 1):
            for l in range(upper + 1):
                # デフォルト　elseで下に置けない（場合分けが難しいので）
                dp[i + 1][j][l] = dp[i][j][l]
                # 追加
                if l >= weight[i]:
                    dp[i + 1][j][l] = max(dp[i][j][l], dp[i][j][l - weight[i]] + value[i])
                # 追加（コストカット）
                if l >= 1 and limit >= 1:
                    # j - 1の段で行ったl >= weight[i]の処理が先に実行されるのでmaxの候補にdp[i + 1][j - 1][l]を入れる
                    dp[i + 1][j - 1][l] = max(dp[i + 1][j - 1][l], dp[i][j - 1][l], dp[i][j][l - 1] + value[i])
    return dp[N][0][upper]

print(knapsack_6(N, A, 1, w, v))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

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

N, A = getNM()
w = []
v = []
for i in range(N):
    a, b = getNM()
    w.append(a)
    v.append(b)

# limit回までコストカットできる
def knapsack_6(N, upper, limit, weight, value):
    dp = [[[0] * (upper + 1) for i in range(limit + 1)] for j in range(N + 1)]

    for i in range(N):
        # ボーナスでコスト１にするのを使ったか 使うと-1する
        for j in range(limit + 1):
            for l in range(upper + 1):
                # デフォルト　elseで下に置けない（場合分けが難しいので）
                dp[i + 1][j][l] = dp[i][j][l]
                # 追加
                if l >= weight[i]:
                    dp[i + 1][j][l] = max(dp[i][j][l], dp[i][j][l - weight[i]] + value[i])
                # 追加（コストカット）
                if l >= 1 and limit >= 1:
                    dp[i + 1][j - 1][l] = max(dp[i + 1][j - 1][l], dp[i][j - 1][l], dp[i][j][l - 1] + value[i])
    return dp[N][0][upper]

print(knapsack_6(N, A, 1, w, v))

Submission status: Accepted

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

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

t -= 1
dp = [[0]*(t+1) for i in range(n+1)]
for i in range(1, n+1):
    ca, cb = ab[i-1][0], ab[i-1][1]
    for j in range(1, t+1):
        if j - ca >= 0:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-ca] + cb)
        else:
            dp[i][j] = dp[i-1][j]

b_max = [0]
tmp = 0
for i in range(n-1, -1, -1):
    tmp = max(tmp, ab[i][1])
    b_max = [tmp] + b_max

ans = 0
for i in range(n+1):
    ans = max(ans, dp[i][t] + b_max[i])
    # print(dp[i][t] + b_max[i])

print(ans)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
A = [0]*N
B = [0]*N
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x: x[0])
dp = [[0]*(T) for _ in range(N+1)]
ans = 0
for i in range(N):
    for j in range(T):
        dp[i+1][j] = dp[i][j]
        ans = max(ans, dp[i][j] + AB[i][1])
        # 上は この時刻jまでで商品i-1個を入れた後に時間制約の無いi個目の商品を追加している
        if j - AB[i][0] >= 0:
            dp[i+1][j] = max(dp[i][j], dp[i][j-AB[i][0]] + AB[i][1])
print(ans)

Submission status: Accepted

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

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

for i in range(N):
    a,b = abl[i]
    for t in range(6001):
        dp[i+1][t] = max(dp[i+1][t], dp[i][t])
        if t < T: dp[i+1][t+a] = max(dp[i][t]+b, dp[i][t+a])


ans = max(dp[N])
print(ans)

Submission status: Accepted

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

abl.sort()
dp = [ [0]*6001 for _ in range(N+1) ]

for i in range(N):
    a,b = abl[i]
    for t in range(6001):
        dp[i+1][t] = max(dp[i+1][t], dp[i][t])
    for t in range(T+1):
        if t < T:
            # dp[i+1][t+a] = max(dp[i+1][t+a], dp[i][t+a])
            dp[i+1][t+a] = max(dp[i][t]+b, dp[i][t+a])


ans = max(dp[N])
print(ans)

Submission status: Accepted

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

dp=[[-10**10]*(t+1) for _ in range(n+1)]
dp[0][0]=0
dp[1][0]=0
ans=ab[0][1]
for i in range(1,n):
    for j in range(t):
        dp[i+1][j]=max(dp[i][j],dp[i][j-ab[i-1][0]]+ab[i-1][1] if j>=ab[i-1][0] else -10**10)
        ans=max(ans,dp[i+1][j]+ab[i][1])

print(ans)

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
a_list = []
for _ in range(N):
    a, b = map(int, input().split())
    a_list.append((a, b))
a_list.sort(key=lambda x: x[0])

dp = [[0 for _ in range(T + 3001)] for _ in range(N + 1)]
for i in range(1, N + 1):
    a, b = a_list[i - 1]
    for j in range(T + 3001):
        dp[i][j] = dp[i - 1][j]
    for j in range(T):
        dp[i][j + a] = max(dp[i - 1][j + a], dp[i - 1][j] + b)
print(max(dp[-1]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, t = LI()
ab = [LI() for _ in range(n)]
ab.sort(key = itemgetter(0))

dp = [[0] * (t+3001) for _ in range(n+1)]
for i in range(1, n+1):
    a, b = ab[i-1]
    for j in range(t + 3001):
        dp[i][j] = dp[i-1][j]
    for j in range(t):
        dp[i][j+a] = max(dp[i-1][j+a], dp[i-1][j] + b)

ans = 0
for i in range(t-1, t + 3001):
    ans = max(ans, dp[n][i])
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    A = [a[0] for a in AB]
    B = [b[1] for b in AB]

    dp1 = [[0]*T for _ in range(N)]
    dp2 = [[0]*T for _ in range(N+2)]

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, T = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
X.sort()
dp = [-1 for _ in range(T+X[-1][0]+10)]
dp[0] = 0
for i in range(N):
  for j in range(T, 0, -1):
    if dp[j-1] != -1:
      dp[j-1+X[i][0]] = max(dp[j-1+X[i][0]], dp[j-1] + X[i][1])
print(max(dp))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, T = mapint()
AB = [list(mapint()) for _ in range(N)]
AB.sort()
maxtime = AB[-1][0]
Bs = [b for a, b in AB]
dp = [0]*(T)

ans = 0
for n in range(N-1):
    a, b = AB[n]
    newdp = [0]*(T)
    for i in range(T):
        if a<=i and i-a<T:
            newdp[i] = max(dp[i], dp[i-a]+b)
    dp = newdp
    ans = max(ans, max(dp)+max(Bs[n+1:]))

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    AB.sort()

    ans = 0
    dp1 = [[0]*(T+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(T):
            t = j - AB[i][0]
            if 0 <= t:
                dp1[i+1][j] = max(dp1[i][j], dp1[i][t] + AB[i][1])
            else:
                dp1[i+1][j] = dp1[i][j]
        ans = max(ans, dp1[i][T-1] + AB[i][1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    A = [a[0] for a in AB]
    B = [b[1] for b in AB]

    dp1 = [[0]*(T+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(T):
            t = j - A[i]
            if 0 <= t:
                dp1[i+1][j] = max(dp1[i][j], dp1[i][t] + B[i])
            else:
                dp1[i+1][j] = dp1[i][j]
    dp2 = [[0]*(T+1) for _ in range(N+2)]
    for i in range(1, N+1)[::-1]:
        for j in range(T):
            t = j - A[i-1]
            if 0 <= t:
                dp2[i][j] = max(dp2[i+1][j], dp2[i+1][t] + B[i-1])
            else:
                dp2[i][j] = dp2[i+1][j]
    ans = 0
    for i in range(N):
        for j in range(T):
            ans = max(ans, dp1[i][j] + dp2[i+2][T - 1 - j] + B[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    AB.sort()
    A = [a[0] for a in AB]
    B = [b[1] for b in AB]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, T = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(N)]
    AB.sort()
    A = [a[0] for a in AB]
    B = [b[1] for b in AB]

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, T, AB):
    dpL = [[0] * (T + 1) for _ in range(N + 2)]
    for i in range(1, N + 1):
        a, b = AB[i - 1]
        for t in range(T):
            dpL[i][t] = dpL[i - 1][t]
            if t >= a:
                dpL[i][t] = max(dpL[i][t], dpL[i - 1][t - a] + b)

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

    ans = 0
    for i in range(1, N + 1):
        a, b = AB[i - 1]
        for t in range(T):
            ans = max(ans, dpL[i - 1][t] + dpR[i + 1][T - 1 - t] + b)
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, T = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]
    main(N, T, AB)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 01ナップサック問題
N,W = map(int,readline().split())
AB = [list(map(int,readline().split())) for i in range(N)]
AB.sort(key=lambda x: x[0])
dp = [0]*(W+1)

for (w,v) in AB:
    dpnew = dp[::]
    for j in range(W):
        dpnew[min(j+w,W)] = max(dp[min(j+w,W)],dp[j] + v)
    dp = dpnew

print(max(dp))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

# 01ナップサック問題
N,W = map(int,readline().split())
AB = [list(map(int,readline().split())) for i in range(N)]
AB.sort(key=lambda x: (x[0],x[1]))
dp = [0]*(W+1)

for (w,v) in AB:
    dpnew = dp[::]
    for j in range(W):
        dpnew[min(j+w,W)] = max(dp[min(j+w,W)],dp[j] + v)
    dp = dpnew

print(max(dp))

Submission status: Accepted

Solution code:
N,T = map(int,input().split())
X = []
for i in range(N):
  a,b = map(int,input().split())
  X.append((a,b))
X.sort()
#print(X)
A = [];B = []
for i in range(N):
  A.append(X[i][0])
  B.append(X[i][1])
dp = [[0 for _ in range(T)] for _ in range(N+1)]
#dp[i][j] i番目までの料理を頼んだ時j分後の最大値
ans = 0
for i in range(N):
  time, aji = X[i]
  for j in range(T):
    if j-time >= 0:
      dp[i+1][j] = max(dp[i][j-time] + aji,dp[i][j])
    else:
      dp[i+1][j] = dp[i][j]
  
  if i < N-1:
    last = max(B[i+1:])
  else:
    last = 0
  #print(ans,last,dp[i+1][T-1])
  ans = max(ans,dp[i+1][T-1]+last)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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