Problem:


Score : 500 points

Problem Statement

Takahashi is at an all-you-can-eat restaurant.

The restaurant offers N kinds of dishes. It takes A_i minutes to eat the i-th dish, whose deliciousness is B_i.

The restaurant has the following rules:

You can only order one dish at a time. The dish ordered will be immediately served and ready to eat.

You cannot order the same kind of dish more than once.

Until you finish eating the dish already served, you cannot order a new dish.

After T-0.5 minutes from the first order, you can no longer place a new order, but you can continue eating the dish already served.

Let Takahashi's happiness be the sum of the deliciousness of the dishes he eats in this restaurant.

What is the maximum possible happiness achieved by making optimal choices?

Constraints

2 \leq N \leq 3000

1 \leq T \leq 3000

1 \leq A_i \leq 3000

1 \leq B_i \leq 3000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N T
A_1 B_1
:
A_N B_N

Output

Print the maximum possible happiness Takahashi can achieve.

Sample Input 1

2 60
10 10
100 100

Sample Output 1

110

By ordering the first and second dishes in this order, Takahashi's happiness will be 110.

Note that, if we manage to order a dish in time, we can spend any amount of time to eat it.

Sample Input 2

3 60
10 10
10 20
10 30

Sample Output 2

60

Takahashi can eat all the dishes within 60 minutes.

Sample Input 3

3 60
30 10
30 20
30 30

Sample Output 3

50

By ordering the second and third dishes in this order, Takahashi's happiness will be 50.

We cannot order three dishes, in whatever order we place them.

Sample Input 4

10 100
15 23
20 18
13 17
24 12
18 29
19 27
23 21
18 20
27 15
22 25

Sample Output 4

145



Sample input:
2 60
10 10
100 100


Sample output:
110

Submission status: Wrong Answer

Solution code:
def examE():
    N, T = LI()
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())
    maxT = max(A)
    dp = [[[0 for _ in range(2)] for _ in range(T+ 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(T+ 1):
            dp[i+1][j][1] = max(dp[i+1][j][1], dp[i][j][0] + B[i])
            if A[i] <= j:
                dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j - A[i]][0] + B[i])
                dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j - A[i]][1] + B[i])
            dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][0])
            dp[i + 1][j][1] = max(dp[i + 1][j][1], dp[i][j][1])

#    print(dp[N][T])
    ans = max(dp[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: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
N, T = map(int, readline().split())
AB = [list(map(int, readline().split())) for _ in range(N)]
A, B = map(list, zip(*AB))
dp = [0]*(T + max(A) + 1)

for i in range(N):
    dp2 = dp[:]
    for t in range(T):
        dp2[t+1] = max(dp2[t+1], dp[t])
        dp2[t+A[i]] = max(dp2[t+A[i]], dp[t] + B[i] )
    dp = dp2[:]
print(max(dp))

Submission status: Wrong Answer

Solution code:
def main():
    n, t = map(int, raw_input().split())
    wv = []
    for _ in xrange(n):
        a, b = map(int, raw_input().split())
        wv.append([a, b])
    wv.sort(key=lambda x: x[1])
    _, best_v = wv.pop()

    dp = [[0] * (t + 1) for _ in xrange(n)]
    used = [[0] * (t + 1) for _ in xrange(n)]
    for i in xrange(n - 2, -1, -1):
        w, v = wv[i]
        for j in xrange(t + 1):
            if j < w:
                dp[i][j] = dp[i + 1][j]
                used[i][j] = used[i + 1][j]
            else:
                a = dp[i + 1][j - w] + v
                if a < dp[i + 1][j]:
                    dp[i][j] = dp[i + 1][j]
                    used[i][j] = used[i + 1][j]
                else:
                    dp[i][j] = a
                    used[i][j] = used[i + 1][j - w] + w
    if used[0][t] < t:
        print dp[0][t] + best_v
    else:
        a = dp[0][t - 1] + best_v
        b = dp[0][t]
        print max(a, b)

main()

Submission status: Wrong Answer

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

xy=ab[-1]

ab=ab[:-1:]
a=[t[0] for t in ab]
b=[t[1] for t in ab]

#print(ab)

dp=[[-1 for _ in range(t)] for _ in range(n)]
for i in range(t):
	dp[0][i]=0

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

#print(dp)
print(dp[-1][-1]+xy[1])

Submission status: Wrong Answer

Solution code:

N,T = map(int,input().split())

tlis = [0] * (T+1)


for i in range(N):

    ntlis = [0] * (T+1)

    A,B = map(int,input().split())

    for j in range(T+1):

        ntlis[j] = max(ntlis[j] , tlis[j])

        if j != T and (j == 0 or tlis[j] != 0):
            ntlis[ min(j + A , T) ] = max(ntlis[ min(j + A , T) ], tlis[j] + B)

    tlis = ntlis.copy()

print (max(tlis))

Submission status: Wrong Answer

Solution code:
import sys
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)
a_mx = max(a)
dp = [0]*(t+a_mx+1)
#dp2 = [i for i in range(t+a_mx)]##注文時間
for i in range(n):
    for s in range(t+a[i]-1,a[i]-1,-1):##時間制限
        if dp[s]<=dp[s-a[i]]+b[i]:
            dp[s] = dp[s-a[i]]+b[i]
#            dp2[s] = s-a[i]
"""
ans = 0
for s in range(t+a_mx,-1,-1):
    if dp2[s]<=t-1 and ans<dp[s]:###-1か？
        ans = dp[s]
"""
print(max(dp))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

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

main()

Submission status: Wrong Answer

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

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

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

print(max(dp))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, T = map(int, input().split())
vw = []
ma, mb = 0, 0
for _ in range(N) :
    A, B = map(int, input().split())
    if B > mb or (B == mb and A > ma) :
        if not ma == mb == 0 :
            vw.append((mb, ma))
        ma, mb = A, B
    else :
        vw.append((B, A))
        
def knapsack(i, w) :
    if (i, w) in dp :
        return dp[(i, w)]
    
    if i == N - 1 : 
        return 0
    elif w < vw[i][1] :
        ret = knapsack(i+1, w)
    else :
        ret = max(knapsack(i+1, w), knapsack(i+1, w-vw[i][1])+vw[i][0])
        
    dp[(i, w)] = ret
    return ret

dp = dict()
print(knapsack(0, T - 2) + mb)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4100000)
import heapq
n,t = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(n)]
heap = []
for i in range(len(a)):
    heapq.heappush(heap, [-a[i][1]/a[i][0], a[i][0], a[i][1]])
ans = 0
maxleft = 0
while t > 0.5 and len(heap) > 0:
    z,x,c = heapq.heappop(heap)
    if t-x > 0.5:
        t -= x
        t -= 0.5
        ans += c
    else:
        maxleft = max(maxleft, c)
print(ans + maxleft)

Submission status: Wrong Answer

Solution code:
n,t=map(int,input().split())
dp=[-1 for i in range(t+1)]
d=[]
dp[0]=0
hozon=[[] for i in range(t+1)]
for i in range(n):
    d.append(list(map(int,input().split())))
d=sorted(d,key=lambda x: -x[1])
for i in range(n):
    for j in range(t,-1,-1):
        if dp[j]>=0 and j+d[i][0]<=t:
            if dp[j+d[i][0]]<dp[j]+d[i][1]:
                dp[j+d[i][0]]=dp[j]+d[i][1]
                hozon[j+d[i][0]]=[i]+hozon[j]
a=max(dp)
ai=dp.index(a)
if ai==t:
    print(a)
    exit()
ah=hozon[ai]
for i in range(n):
    if not i in ah:
        print(a+d[i][1])
        exit()
print(a)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

DP=[[0,0] for i in range(T+1)]

for ind,(x,y) in enumerate(D):
    for time in range(T,-1,-1):
        if time-x>=0 and DP[time][0]<DP[time-x][0]+y:

            if DP[time][1]==ind:
                DP[time]=[DP[time-x][0]+y,ind+1]
            else:
                DP[time][0]=DP[time-x][0]+y

D.append((0,0))
                
ANS=DP[-1][0]

for x,y in DP[:-1]:
    if x==0:
        continue
    ANS=max(ANS,x+D[y][1])

print(ANS)

Submission status: Wrong Answer

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()])
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: Wrong Answer

Solution code:
n,t = map(int,input().split())
dp = [[0 for _ in range(t+2)]]
for _ in range(n):
  w,v = map(int,input().split())
  tmp = [0]
  for f in range(1,t+1):
    #tmp.append(max(tmp[-1],dp[-1][f-w]+v))
    if f - w >= 0:
      if dp[-1][f-w] + v > dp[-1][f]:
        tmp.append(dp[-1][f-w] + v)
      else:
        tmp.append(dp[-1][f])
    else:
      tmp.append(dp[-1][f])
  tmp.append(max(dp[-1][-1],dp[-1][-3]+v))
  dp.append(tmp)
print(max(dp[-1][-1],dp[-1][-2]))
#for x in dp:
  #print('#',x)

Submission status: Wrong Answer

Solution code:
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値
N, T = map(int, input().split())
items = sorted([tuple(map(int, input().split()))
                for i in range(N)], key=lambda x: x[1])

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

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

        # これは配るDP

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        if 0 <= t_sum-items[i][0] < T:
            dp[i+1][t_sum] = max(dp[i+1][t_sum],
                                 dp[i][t_sum-items[i][0]]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][t_sum] = max(dp[i+1][t_sum], dp[i][t_sum])

ans = 0
for t in range(T+3003):
    ans = max(ans, dp[N][t])
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
def solve():

    N, T = map(int, input().split())
    dp = [0 for _ in range(T+1)]
    for _ in range(N):
        a, b = map(int, input().split())
        for t in range(T-1, -1, -1):
            dp[min(T,t+a)] = max(dp[t]+b, dp[min(T,t+a)])
    return dp[T]

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

Submission status: Wrong Answer

Solution code:

import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    N, T = map(int,input().split())
    F = [list(map(int,input().split())) for k in range(N)]

    F = sorted(F, key = lambda x: -x[1])
    t = F.pop(0)

    weight = [0 for k in range(N)]
    value = [0 for k in range(N)]
    for k in range(N-1):
        weight[k] = F[k][0]
        value[k] = F[k][1]

    dp = [[-10000000 for i in range(T+1)] for j in range(N+1)]

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

    for i in range(N-1):
        for w in range(T):
            if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
            else: #入る可能性はない
                dp[i+1][w]=dp[i][w]
    print(dp[N-1][T-1] + t[1])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, T = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())
    M = T+max(A)
    dp = [[(0, 0)] * M for _ in range(2)]
    for i in range(N):
        a, b = A[i], B[i]
        for j in range(M):
            dp[i & 1][j] = dp[(i-1) & 1][j]
        for j in range(a, M):
            t, m = dp[(i-1) & 1][j-a]
            t += b
            m = max(m, a)
            if j - m < T and dp[i & 1][j][0] < t:
                dp[i & 1][j] = (t, m)
    ans = 0
    for i in range(M):
        ans = max(ans, dp[(N-1) & 1][i][0])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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)]
    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: Wrong Answer

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

n,t = map(int,input().split())
dg = 10**5

ab = []
tank = -1

for i in range(n):
    a,b = map(int,input().split())
    if a >= t:
        tank = max(tank,b)
    else:
        ab.append(b*dg+a)
ab.sort()

n = len(ab)

#print(ab)

if len(ab) == 0:
    print(tank)
    exit()

dp = [[0]*(t+1) for i in range(n)]

for i in range(n):
    a,b = ab[i]%dg,ab[i]//dg
    for j in range(min(a,t+1)):
        dp[i][j] = dp[i-1][j]
    for j in range(a,t+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-a]+b)

if len(ab) == 1:
    a,b = ab[0]%dg,ab[0]//dg
    print(b+tank)
    exit()

res = dp[n-1][t]

if tank > 0:
    res += tank


p = 0
q = 0
for k in range(n-1,0,-1):
    a,b = ab[k]%dg,ab[k]//dg
    q += b
    res = max(res,q+dp[k-1][t-p-1])
    p += a
    if p >= t:
        break
print(res)

Submission status: Wrong Answer

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

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

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

for i in range(N):
    a, b = AB[i]
    # print(a, b)
    for j in range(T):
        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
            )

# for dp_i in dp:
#     print(dp_i)

print(dp[N][T])

Submission status: Wrong Answer

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()])
aa = t+max([i[0] for i in ab])
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: Wrong Answer

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

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

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

for i in range(N):
    a, b = AB[i]
    print(a, b)
    for j in range(T):
        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
            )

# for dp_i in dp:
#     print(dp_i)

print(dp[N][T])

Submission status: Wrong Answer

Solution code:
import numpy as np

def knapsack2(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(2*W+1)] for j in range(N+1)]
  for i in range(2*W+1):
      dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(2*W+1):
      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]
  return np.max(np.array(dp))
  #return dp[N][2*W]

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

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

Submission status: Wrong Answer

Solution code:
import sys
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)
a_mx = max(a)
dp = [0]*(t+1+a_mx)
dp2 = [i for i in range(t+1+a_mx+1)]##注文時間
for i in range(n):
    for s in range(t+a[i],a[i]-1,-1):##時間制限
        if dp[s]<=dp[s-a[i]]+b[i]:
            dp[s] = dp[s-a[i]]+b[i]
            dp2[s] = s-a[i]

ans = 0
for s in range(t+a_mx+1,-1,-1):
    if dp2[s]<=t-1 and ans<dp[s]:###-1か？
        ans = dp[s]
print(ans)

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
time = [-1 for i in range(6030)]
time[0] = 0
now = 0
lis = [list(map(int,input().split())) for i in range(n)]
lis.sort(key = lambda x:x[1])
for i in range(n):
    for j in range(t-1,-1,-1):
        if time[j] != -1:
            time[j+lis[i][0]] = max(time[j+lis[i][0]],time[j]+lis[i][1])
print(max(time))

Submission status: Wrong Answer

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

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

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

#for x in dp: print(x)
ans = max(max(dp[n]), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
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)]
    ans=-INF

    # 時間が最もかかるもののうち、価値が最大のものを最後にする
    AB.sort()
    la,lb=AB[-1]

    dp=[0]*T
    for i in range(n-1):
        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)
        dp=ndp
    ans=max(ans,max(dp)+lb)

    # 価値が最大のもののうち、時間が最もかかるものを最後にする
    AB.sort(lambda x:(x[1],x[0]))
    la,lb=AB[-1]

    dp=[0]*T
    for i in range(n-1):
        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)
        dp=ndp
    ans=max(ans,max(dp)+lb)

    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
n,t=map(int,input().split())
dp=[-1 for i in range(t+1)]
d=[]
dp[0]=0
hozon=[[] for i in range(t+1)]
for i in range(n):
    d.append(list(map(int,input().split())))
d=sorted(d,key=lambda x: -x[1])
for i in range(n):
    for j in range(t,-1,-1):
        if dp[j]>=0 and j+d[i][0]<=t:
            if dp[j+d[i][0]]<dp[j]+d[i][1]:
                dp[j+d[i][0]]=dp[j]+d[i][1]
                hozon[j+d[i][0]]+=[i]
a=max(dp)
ai=dp.index(a)
if ai==t:
    print(a)
    exit()
ah=hozon[ai]
for i in range(t+1):
    if not i in ah:
        print(a+d[i][1])
        exit()

Submission status: Wrong Answer

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

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

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

for x in dp: print(x)
ans = max(max(dp[n]), ans)
print(ans)

Submission status: Wrong Answer

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


dp = [0]*(t+1)

for a,b in ab:
    c = max(dp[max(0,t-a):t])
    dp[-1] = max(dp[-1],c+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)
print(max(dp))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

def loop(ab):
    time,ans = 0,0
    i = 0
    while time < t and i < n:
        a,b = ab[i]
        ans += b
        time += a
        i += 1
    return ans

a = sorted(ab,key=itemgetter(1),reverse=True)
b = sorted(ab,key=itemgetter(0))

print(max(loop(a),loop(b)))

Submission status: Wrong Answer

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

n,t = map(int,input().split())
dg = 10**5

ab = []
tank = -1

for i in range(n):
    a,b = map(int,input().split())
    if a > t:
        tank = max(tank,b)
    else:
        ab.append(b*dg+a)
ab.sort()

n = len(ab)

if len(ab) == 0:
    print(tank)
    exit()

dp = [[0]*(t+1) for i in range(n)]

for i in range(n):
    a,b = ab[i]%dg,ab[i]//dg
    for j in range(min(a,t+1)):
        dp[i][j] = dp[i-1][j]
    for j in range(a,t+1):
        dp[i][j] = max(dp[i-1][j],dp[i-1][j-a]+b)

if len(ab) == 1:
    a,b = ab[i]%dg,ab[i]//dg
    print(b+tank)
    exit()

res = dp[n-1][t]

if tank > 0:
    res += tank



p = 0
q = 0
for k in range(n-1,0,-1):
    a,b = ab[k]%dg,ab[k]//dg
    q += b
    res = max(res,q+dp[k-1][t-p-1])
    p += a
    if p >= t:
        break
print(res)

Submission status: Wrong Answer

Solution code:
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]*3000 for i in range(N)]
for n in range(N-1):
    for w in range(3000):
        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]
ans = 0
for w in range(T):
    ans = max(ans,dp[N-1][w]+AB[N-1][1])
print(ans)

Submission status: Wrong Answer

Solution code:
n, t, *L = map(int, open(0).read().split())
d = [0] * (t + max(L[::2]))
for w, v 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: Wrong Answer

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

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

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

print(max(dp))

Submission status: Wrong Answer

Solution code:
n,t = map(int,input().split())
time = [-1 for i in range(6030)]
time[0] = 0
now = 0
for i in range(n):
    a,b = map(int,input().split())
    for j in range(t-1,-1,-1):
        if time[j] != -1:
            time[j+a] = max(time[j+a],time[j]+b)
print(max(time))

Submission status: Wrong Answer

Solution code:
import sys
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)
a_mx = max(a)
dp = [0]*(t+1+a_mx)
dp2 = [i for i in range(t+1+a_mx+1)]##注文時間
for i in range(n):
    for s in range(t+a[i],a[i]-1,-1):##時間制限
        if dp[s]<=dp[s-a[i]]+b[i]:
            dp[s] = dp[s-a[i]]+b[i]
            dp2[s] = s-a[i]

ans = 0
for s in range(t+a_mx+1,-1,-1):
    if dp2[s]<=t and ans<dp[s]:
        ans = dp[s]
print(ans)

Submission status: Wrong Answer

Solution code:
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値
N, T = map(int, input().split())
items = sorted([tuple(map(int, input().split()))
                for i in range(N)], key=lambda x: x[1])

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

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

        # これは配るDP

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        dp[i+1][t_sum+items[i][0]] = max(dp[i+1][t_sum+items[i][0]],
                                         dp[i][t_sum]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][t_sum] = max(dp[i+1][t_sum], dp[i][t_sum])

ans = 0
for t in range(T+3003):
    ans = max(ans, dp[N][t])
print(ans)

Submission status: Wrong Answer

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()])
c = [0] * (t*3)
for i in ab:
    d = c[:]
    for j in range(t):
        k = d[j]
        l = i[0] + j
        if l >= 3*t:
            continue
        c[l] = max(c[l], d[j] + i[1])
print(max(c))

Submission status: Wrong Answer

Solution code:
n, t, *L = map(int, open(0).read().split())
d = [0] * (t + max(L[::2]))
for w, v 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[t - 1:]))

Submission status: Wrong Answer

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

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

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

D.append([0,0])

DP=[[0,0] for i in range(T+1)]

for ind,(x,y) in enumerate(D):
    for time in range(T,-1,-1):
        if time-x>=0 and DP[time][0]<DP[time-x][0]+y:

            if DP[time][1]==ind:
                DP[time]=[DP[time-x][0]+y,ind+1]
            else:
                DP[time][0]=DP[time-x][0]+y
                

ANS=DP[-1][0]

for x,y in DP[:-1]:
    if x==0:
        continue
    ANS=max(ANS,x+D[y][1])

print(ANS)

Submission status: Wrong Answer

Solution code:
# dp[i][w_sum]: i番目までの品物で重さがw_sumを超えないように選んだときの、価値の総和の最大値
N, T = map(int, input().split())
items = sorted([tuple(map(int, input().split()))
                for i in range(N)], key=lambda x: x[0])

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

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

        # これは配るDP

        # i-1番目の品物を選ぶ場合
        # 重量的に入れられるなら入れてみる
        dp[i+1][t_sum+items[i][0]] = max(dp[i+1][t_sum+items[i][0]],
                                         dp[i][t_sum]+items[i][1])

        # i-1番目の品物を選ばない場合
        dp[i+1][t_sum] = max(dp[i+1][t_sum], dp[i][t_sum])

ans = 0
for t in range(T+3003):
    ans = max(ans, dp[N][t])
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N,T = II()
A,B = Line(N,2)

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

for i in range(N):
    for t in range(T):
        if i==0:
            if t-0.5>=A[i]:
                m1[i][t] = B[i]
            else:
                pass
        else:
            if t-0.5>=A[i]:
                m1[i][t] = max(m1[i-1][t-A[i]]+B[i], m1[i-1][t])
            else:
                m1[i][t] = m1[i-1][t]

for i in range(N):
    for t in range(T):
        if i==0:
            m2[i][t] = B[i]
        else:
            val1 = m1[i-1][t] + B[i]
            if t-A[i]>=0:
                val2 = max(m2[i-1][t], m2[i-1][t-A[i]]+B[i])
            else:
                val2 = m2[i-1][t]
            m2[i][t] = max(val1,val2)

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

Submission status: Wrong Answer

Solution code:
def examE():
    N, T = LI()
    A, B = [0] * N, [0] * N
    for i in range(N):
        A[i], B[i] = map(int, input().split())
    maxT = max(A)
    dp = [[[0,0] for _ in range(T+maxT + 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(T+maxT + 1):
            if A[i] <= j:
                dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j - A[i]][0] + B[i])
                if A[i]>dp[i][j - A[i]][1]:
                    dp[i + 1][j][1] = A[i]
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    for i in range(maxT):
        if dp[N][T+i+1][1]>=(i+1):
            dp[N][T][0] = max(dp[N][T][0], dp[N][T+i+1][0])
#    print(dp)
    ans = max(dp[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: Wrong Answer

Solution code:
n,t = map(int,input().split())
c = [tuple(map(int,input().split())) for _ in range(n)]
c.sort(key=lambda x: -x[1])
dp = [[-1]*t for _ in range(n+1)]
dp[0][0] = 0
for r in range(n):
    a,b = c[r]
    for i in range(t):
        if dp[r][i] >= 0:
            dp[r+1][i] = dp[r][i]
            if i+a < t and dp[r+1][i+a] < dp[r][i] + b:
                dp[r+1][i+a] = dp[r][i] + b
ct,id = 0,0
for i in range(t):
    if ct < dp[-1][i]:
        id = i
        ct = dp[-1][i]
ans = dp[-1][id]
cr = n
s = set()
while cr > 0 and id > 0:
    while cr > 0 and dp[cr][id] == dp[cr-1][id]:
        cr -= 1
    if cr:
        cr -= 1
        s.add(cr)
        id -= c[cr][0]
lis = enumerate(c)
for id, x in lis:
    if id not in s:
        ans += x[1]
        break
print(ans)