Problem:


Score : 100 points

Problem Statement

There are N blocks, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N), Block i has a weight of w_i, a solidness of s_i and a value of v_i.

Taro has decided to build a tower by choosing some of the N blocks and stacking them vertically in some order.
Here, the tower must satisfy the following condition:

For each Block i contained in the tower, the sum of the weights of the blocks stacked above it is not greater than s_i.

Find the maximum possible sum of the values of the blocks contained in the tower.

Constraints

All values in input are integers.

1 \leq N \leq 10^3

1 \leq w_i, s_i \leq 10^4

1 \leq v_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
w_1 s_1 v_1
w_2 s_2 v_2
:
w_N s_N v_N

Output

Print the maximum possible sum of the values of the blocks contained in the tower.

Sample Input 1

3
2 2 20
2 1 30
3 1 40

Sample Output 1

50

If Blocks 2, 1 are stacked in this order from top to bottom, this tower will satisfy the condition, with the total value of 30 + 20 = 50.

Sample Input 2

4
1 2 10
3 1 10
2 4 10
1 6 10

Sample Output 2

40

Blocks 1, 2, 3, 4 should be stacked in this order from top to bottom.

Sample Input 3

5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000

Sample Output 3

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 4

8
9 5 7
6 2 7
5 7 3
7 8 8
1 9 6
3 3 3
4 1 7
4 5 5

Sample Output 4

22

We should, for example, stack Blocks 5, 6, 8, 4 in this order from top to bottom.



Sample input:
3
2 2 20
2 1 30
3 1 40


Sample output:
50

Submission status: Time Limit Exceeded

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

N=int(input())
B=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[0]+x[1])
#W+Sの順にソートすると無駄がない。

DP=[0]*(10**4+2)
#重さの合計がWのときの価値。
#W=10**4+1ならそれ以上更新されないので、W>=10**4+1以上のものはそこに置く

for w,s,v in B:
    
    if 10**4+1-w<=s:
        if DP[-1]<max(DP[10**4+1-w:s+1])+v:
            DP[-1]=max(DP[10**4+1-w:s+1])+v
        
    for i in range(min(10**4-w,s),-1,-1):
        if DP[i+w]<DP[i]+v:
            DP[i+w]=DP[i]+v

print(max(DP))

Submission status: Time Limit Exceeded

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

N=int(input())
B=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x:x[0]+x[1])
#W+Sの順にソートすると無駄がない。

DP=[0]*(10**4+2)
#重さの合計がWのときの価値。
#W=10**4+1ならそれ以上更新されないので、W>=10**4+1以上のものはそこに置く

for w,s,v in B:
    
    if 10**4+1-w<=s:
        x=max(DP[10**4+1-w:s+1])+v
        if DP[-1]<x:
            DP[-1]=x
        
    for i in range(min(10**4-w,s),-1,-1):
        if DP[i+w]<DP[i]+v:
            DP[i+w]=DP[i]+v

print(max(DP))

Submission status: Time Limit Exceeded

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

N=int(input())
B=[list(map(int,input().split())) for i in range(N)]

B.sort(key=lambda x:x[0]+x[1])
#W+Sの順にソートすると無駄がない。

DP=[0]*(10**4+2)
#重さの合計がWのときの価値。
#W=10**4+1ならそれ以上更新されないので、W>=10**4+1以上のものはそこに置く

for w,s,v in B:
    for i in range(s,-1,-1):
        if i+w<=10**4:
            if DP[i+w]<DP[i]+v:
                DP[i+w]=DP[i]+v

        else:
            if DP[-1]<DP[i]+v:
                DP[-1]=DP[i]+v

print(max(DP))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]
src.sort(key=lambda x:x[0]+x[1])

dp = [None] * (20001)
dp[0] = 0
for w,s,v in src:
    for s0 in range(s,-1,-1):
        if dp[s0] is None: continue
        if dp[s0+w] is None:
            dp[s0+w] = dp[s0] + v
        else:
            dp[s0+w] = max(dp[s0+w], dp[s0] + v)
print(max(v for v in dp if v is not None))

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())
blocks = []
for line in sys.stdin.readlines():
    w, s, v = map(int, line.split())
    blocks.append((w + s, w, s, v))
blocks.sort()

dp = [-1] * 20001
dp[0] = 0
for _, w, s, v in blocks:
    for i in range(min(s, 20000 - w), -1, -1):
        dp[i + w] = max(dp[i + w], dp[i] + v)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
readline = open(0).readline
write = open(1, 'w').write

N = int(readline())
P = [list(map(int, readline().split())) for i in range(N)]
P.sort(key=lambda x: x[0]+x[1])

L = 10**5
dp = [0]*L
for w, s, v in P:
    for i in range(s+w, w-1, -1):
        dp[i] = max(dp[i], dp[i-w] + v)
write("%d\n" % max(dp))

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


n = val()
l = []
for i in range(n):l.append(li())

l.sort(key = lambda x:x[1] + x[0])

dp = [0] * (20001)

for i in l:
    for j in range(i[1], -1, -1):
        dp[j + i[0]] = max(dp[j + i[0]], dp[j] + i[-1])

print(max(dp))

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

#####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 = I()
data = ILL(N)
data.sort(lambda x:x[0]+x[1])
wmax = 22000
dp = [0 for w in range(wmax)]

for i in range(N):
  w,s,v = data[i]
  for j in range(s+1)[::-1]:
    dp[j+w] = max(dp[j+w],dp[j]+v)
print(max(dp))

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	n = int(rl())
	A = []
	mw, ms = 0, 0
	for _ in range(n):
		w, s, v = rli()
		mw, ms = max(mw, w), max(ms, s)
		A.append((w, s, v))
	ans = 0
	A.sort(key = lambda I: (I[0] + I[1]))
	maxs = mw + ms + 100
	dp = [0 for _ in range(maxs+1)]
	for w, s, v in A:
		for i in range(maxs, -1, -1):
			if i - w < 0: break
			if i - w > s: continue
			dp[i] = max(dp[i], dp[i-w] + v)
			ans = max(ans, dp[i])	
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	n = int(rl())
	A = []
	for _ in range(n):
		w, s, v = rli()
		A.append((w, s, v))
	ans = 0
	A.sort(key = lambda I: (I[0] + I[1]))
	maxs = 2*10**4 + 100
	dp = [0 for _ in range(maxs+1)]
	for w, s, v in A:
		for i in range(maxs, -1, -1):
			if i - w < 0: continue
			if i - w > s: continue
			dp[i] = max(dp[i], dp[i-w] + v)
			ans = max(ans, dp[i])	
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
wsv = [list(map(int,readline().split())) for _ in range(n)]
wsv.sort(key=lambda x:x[0]+x[1])

dp = [[0] * (2*10**4+1) for _ in range(n+1)]
for i in range(n):
    wi,si,vi = wsv[i]
    for j in range(1,2*10**4+1):
        if(j < wi):
            dp[i+1][j] = max(dp[i+1][j-1],dp[i][j])
        elif(j <= wi+si):
            dp[i+1][j] = max(dp[i+1][j-1],dp[i][j],dp[i][j-wi]+vi)
        else:
            dp[i+1][j] = max(dp[i+1][j-1],dp[i][j])

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

Submission status: Accepted

Solution code:

def resolve():
    from functools import cmp_to_key
    # aをbの上に配置するとき、W≤sa と W+wa≤sbを満たす必要: W≤min(sa,sb−wa)
    # bをaの上に配置するとき、同様に: W≤min(sb,sa−wb)
    def cmp(a, b):
        va = min(a[1], b[1] - a[0])
        vb = min(b[1], a[1] - b[0])
        if (va == vb): return 0
        return -1 if (va > vb) else 1

    N = int(input())
    # Block[w][s][v]
    Block = [list(map(int, input().split())) for _ in range(N)]
    Block.sort(key=cmp_to_key(cmp))

    max_W = 2*(10**4+1)
    dp = [[0]*(max_W+5) for _ in range(N+1)]
    # dp[i][tot] := i番目までを使って、重さの総和がtotである場合の価値の総和の最大値
    for i in range(N):
        w, s, v = Block[i]
        for tot in range(max_W):
            dp[i+1][tot] = max(dp[i+1][tot], dp[i][tot])
            if tot <= s:
                dp[i + 1][tot+w] = max(dp[i + 1][tot+w], dp[i][tot] + v)

    print(max(dp[N]))


if __name__ == "__main__":
    resolve()

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 = int(input())
wsv = [None]*n
for i in range(n):
    wsv[i] = tuple(map(int, input().split()))
wsv.sort(key=lambda x: x[0]+x[1])
ms = max(item[1] for item in wsv) + max(item[0] for item in wsv)
dp = [[0]*(ms+1) for _ in range(n+1)]
for i in range(1, n+1):
    w,s,v = wsv[i-1]
    for j in range(1, ms+1):
        dp[i][j] = dp[i-1][j]
        if j>=w and s>=j-w:
            dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)
ans = max(dp[n][w] for w in range(ms+1))
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
WSV = list(tuple(map(int, input().split())) for _ in range(N))
WSV.sort(key=lambda x: x[0] + x[1])
 
 
U = 2 * 10 ** 4 + 100
dp = np.zeros(U, dtype=np.int64)
for w, s, v in WSV:
    dp[w:w+s+1] = np.maximum(dp[w:w+s+1], dp[:s+1] + v)
 
print(dp.max())

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
WSV = list(tuple(map(int, input().split())) for _ in range(N))
WSV.sort(key=lambda x: x[0] + x[1])
U = 2 * 10 ** 4 + 100
dp = np.zeros(U, dtype=np.int64)
for w, s, v in WSV:
    dp[w:w+s+1] = np.maximum(dp[w:w+s+1], dp[:s+1] + v)
print(dp.max())

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
WSV = list(tuple(map(int, input().split())) for _ in range(N))
WSV.sort(key=lambda x: x[0] + x[1])


U = 2 * 10 ** 4 + 100
dp = np.zeros(U, dtype=np.int64)
for w, s, v in WSV:
    dp[w:w+s+1] = np.maximum(dp[w:w+s+1], dp[:s+1] + v)

print(dp.max())

Submission status: Accepted

Solution code:


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    assume s1 was bottom
    s1-w0 > s0-w1 better solidness
    s1+w1 > s0+w0
    otherwise
    s1+w1 < s0+w0

    OPT[i][j] - maximum value up to i-th brick with weight j
    OPT[i][j] = OPT[i-1][j-w[i]]+v[i] if we take i-th brick, 0 <= j-w[i] <= s[i]
                OPT[i-1][j]
    OPT[0][w[0]] = v[0], otherwise OPT[0][j] = 0
    """
    N = read_int()
    pairs = []
    max_w = 0
    max_s = 0
    for _ in range(N):
        w0, s0, v0 = read_ints()
        max_w = max(max_w, w0)
        max_s = max(max_s, s0)
        pairs.append((s0+w0, w0, s0, v0))
    MAX_WEIGHT = max_w+max_s+1
    pairs.sort()
    OPT = [
        [0]*MAX_WEIGHT for _ in range(N)
    ]
    OPT[0][pairs[0][1]] = pairs[0][3]
    for i in range(1, N):
        for j in range(MAX_WEIGHT):
            OPT[i][j] = max(OPT[i][j], OPT[i-1][j])
            if 0 <= j-pairs[i][1] <= pairs[i][2]:
                OPT[i][j] = max(OPT[i][j], OPT[i-1][j-pairs[i][1]]+pairs[i][3])
    return max(OPT[-1])


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

Submission status: Accepted

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

def solve():
    N = int(input())
    items = [tuple(map(int, input().split())) for _ in range(N)]

    capW = max([w+s for w, s, v in items])
    items.sort(key=lambda x: x[0]+x[1])

    def knapsack01(items, capW):
        dp = [0] * (capW+1)
        for wi, si, vi in items:
            for w in reversed(range(wi, si+wi+1)):
                v0 = dp[w-wi] + vi
                if v0 > dp[w]:
                    dp[w] = v0
        return max(dp)

    ans = knapsack01(items, capW)
    print(ans)


solve()

Submission status: Accepted

Solution code:
n = int(input())
wsv = [list(map(int,input().split())) for i in range(n)]
wsv.sort(key = lambda x:x[0]+x[1],reverse=True)
smx = max(list(zip(*wsv))[1])
dp = [[0 for i in range(smx+1)] for j in range(n+1)]
for i in range(1,n+1):
  dp[i] = dp[i-1][:]
  w,s,v = wsv[i-1]
  dp[i][s] = max(dp[i-1][s],v)
  for ss in range(smx+1)[::-1]:
    sn = min(ss-w,s)
    if sn >= 0 and dp[i-1][ss]:
      dp[i][sn] = max(dp[i][sn],dp[i-1][sn],dp[i-1][ss]+v)
print(max(dp[-1]))

Submission status: Accepted

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

N = int(input())
wsv = [tuple(map(int, input().split())) for _ in range(N)]
wsv.sort(key=lambda t: t[0]+t[1])
dp = [[0]*(2*10**4+1) for _ in range(N+1)]

for i in range(N):
    w, s, v = wsv[i]
    
    for j in range(2*10**4+1):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        
        if s>=j and j+w<=2*10**4:
            dp[i+1][j+w] = max(dp[i+1][j+w], dp[i][j]+v)

print(max(dp[N]))

Submission status: Accepted

Solution code:

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    
    """
    dp[i][j]はi番目までで，重さ合計がjとなるときの価値の最大値にしたい．
    s<10**4　なので，jは10**4 + 10**4まで．
    ただし，上から積む時に実際には優先度がつくので，重りを適切な基準でソートすべき．
    
    現状，重さがXで，a番目とj番目を使うとして，
    「X,a,bの順番ならおけるけど，X,b,aの順だとおけない」
    という状況を考える．
    
    この時，S_j>=X+w_i かつ，s_i<X+w_j　なので．
    S_j - w_i >= X > s_i - w_j　である．
    Xを消去して移項すると，
    s_j+w_j > s_i+w_i
    
    これを基準にソートですね．
    
    """
    N=I()
    wsv=[]
    for i in range(N):
        w,s,v=MI()
        wsv.append([w,s,v])
        
    wsv.sort(key=lambda x:(x[0]+x[1]))
    
    N2=2*(10**4) +1
    dp=[[0]*N2 for _ in range(N+1)]
    
    for i in range(N):
        w,s,v=wsv[i]
        for j in range(N2):
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
            if s>=j and j+w<=(N2-1):
                dp[i+1][j+w]=max(dp[i+1][j+w],dp[i][j]+v)
                
    print(max(dp[-1]))
            
        

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

def resolve():
    n = int(input())
    WSV = [tuple(map(int, input().split())) for _ in range(n)]
    WSV.sort(key = lambda tup:tup[0] + tup[1])

    # dp[i][w] : i 番目まで見て、total weight が w のときの max value
    # solid_max <= 10^4 なので、total weight > 10^4 は考えなくて良い
    res = 0
    solid_max = 10 ** 4
    dp = [-1] * (solid_max + 1)
    dp[0] = 0

    for w0, s0, v in WSV:
        for w in range(solid_max, -1, -1):
            if dp[w] == -1:
                continue
            if w > s0: # w <= s0
                continue
            if w + w0 > solid_max:
                res = max(res, dp[w] + v)
            else:
                dp[w + w0] = max(dp[w + w0], dp[w] + v)

    res = max(res, max(dp))
    print(res)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
a.sort(key = lambda x: -(x[0] + x[1]))

dp = [0] * (a[0][1] + a[0][0] + 1)

for i in range(N):
  w, s, c = a[i]
  for j in range(a[0][1] + a[0][0] + 1):
    if j >= w:
      x = min(j - w, s)
      dp[x] = max(dp[x], dp[j] + c)
print(max(dp))

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
n = int(input())
b = [tuple(map(int, input().split())) for _ in range(n)]
b.sort(key=lambda x: x[0]+x[1])

dp = [0 for _ in range(20010)]
dp[0] = 0

for i in range(n):
	for j in range(b[i][1] + b[i][0], b[i][0]-1, -1):
		dp[j] = max(dp[j], dp[j - b[i][0]] + b[i][2])

print(max(dp))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().strip()

n = int(input())
wsv = [list(map(int, input().split())) for i in range(n)]
wsv.sort(key=lambda x: x[0]+x[1])

max_s = 10**4
DP = [-float("inf")]*(2*max_s+1)

DP[0] = 0

for i in range(n):
    w,s,v = wsv[i]
    nxt = DP[:]
    for j in range(s+1):
        nxt[j+w] = max(DP[j]+v, nxt[j+w])
    DP = nxt

ans = max(DP)
print(ans)

Submission status: Accepted

Solution code:
N, = map(int, input().split())
Xs = []
for i in range(N):
    X, Y, Z = map(int, input().split())
    Xs.append((X,Y,Z,i))
Xs.sort(key=lambda x : x[0]+x[1])

dp = [0]*(2*(10**4)+1)
for x,y,z,i in Xs:
#    print(i+1,x,y,z)
    for i in range(y+1):
        i = y-i
        dp[i+x] = max(dp[i+x], dp[i]+z)
#    print(dp[:10])
print(max(dp))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    wsv = []
    for _ in range(N):
        w, s, v = map(int, input().split())
        wsv.append((w, s, v))
    wsv.sort(key=lambda x: x[0] + x[1])

    inf = 1000000007
    dp = [[-inf] * 20001 for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        w, s, v = wsv[i]
        for j in range(20001):
            if dp[i][j] != -inf:
                dp[i+1][j] = max(dp[i+1][j], dp[i][j])
                if j <= s:
                    dp[i+1][j+w] = max(dp[i+1][j+w], dp[i][j] + v)
    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
blocks = [list(map(int, input().split())) for _ in range(n)]
blocks.sort(key=lambda x: x[0] + x[1])
res = 0
dp = [0] * 20123
# dp[i] - best score of boxes with total weight i
for w, s, v in blocks:
    for j in range(s, -1, -1):
        dp[j + w] = max(dp[j + w], dp[j] + v)
        res = max(res, dp[j + w])
print(res)

Submission status: Accepted

Solution code:
from operator import itemgetter


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]

max_s = 0
for i in range(n):
    w, s, _ = info[i]
    max_s = max(max_s, s)
    info[i].append(s + w)
info = sorted(info, key = itemgetter(3))

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

for i in range(n):
    w, s, v, _ = info[i]
    for j in range(20010):
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
        if s - j >= 0:
            dp[i+1][j+w] = max(dp[i][j] + v, dp[i+1][j+w])
print(max(dp[n]))

Submission status: Accepted

Solution code:
import numpy as np
import sys

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n = int(input())
    wsv = LLI(n)
    wsv.sort(key=lambda x: x[0] + x[1])
    m = wsv[-1][0] + wsv[-1][1] + 1
    dp = np.zeros(m, dtype="i8")
    for w, s, v in wsv:
        np.maximum(dp[s + w:w - 1:-1], dp[s::-1] + v, out=dp[s + w:w - 1:-1])
    print(np.max(dp))

main()

Submission status: Accepted

Solution code:
from functools import cmp_to_key
def cmp(a, b):
    w1, s1, v1 = a
    w2, s2, v2 = b
    if min(s1, s2-w1)>min(s2, s1-w2):
        return 1
    else:
        return -1
N = int(input())
dp = [[0]*10001 for _ in range(N)]
wsv = []
for _ in range(N):
    w, s, v = map(int, input().split())
    wsv.append((w, s, v))
wsv.sort(key = lambda x:-(x[0]+x[1]))
w, s, v = wsv[0]
dp[0][s] = v
for i in range(N-1):
    w, s, v = wsv[i+1]
    for j in range(10001):
        if j>=w:
            dp[i+1][min(s, j-w)] = max(dp[i][j]+v, dp[i+1][min(s, j-w)])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    dp[i+1][s] = max(dp[i+1][s], v)
print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

"""
・最適解をとって2つ入れ替えの議論
・s+wが小さい方が上にあるように詰めることが分かる
・wの和 -> vの和でdp
・自身の下に積むならば、wの和<=s_maxでなければいけない
"""

N = int(readline())
m = map(int,read().split())
WSV = sorted(zip(m,m,m),key=lambda x:x[0]+x[1])

dp = np.zeros(10**4*2+100,np.int64)

for w,s,v in WSV:
    prev = dp
    dp = np.zeros_like(prev)
    # 置く場合
    dp[w:w+s+1] = prev[:s+1]+v
    np.maximum(dp,prev,out=dp)

answer = dp.max()
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from functools import cmp_to_key
    n=int(input())
    B=[list(map(int,input().split())) for _ in range(n)]
    def cmp(a,b):
        va=min(a[1],b[1]-a[0])
        vb=min(b[1],a[1]-b[0])
        if(va==vb): return 0
        return -1 if(va>vb) else 1
    B.sort(key=cmp_to_key(cmp))
    maxS=20000
    dp=[-INF]*(maxS+1)
    dp[0]=0
    for i in range(n):
        w,s,v=B[i]
        ndp=dp[:]
        for total in range(maxS+1):
            if(total<=s and total+s<=maxS):
                ndp[total+w]=max(ndp[total+w],dp[total]+v)
        dp=ndp[:]
    print(max(dp))
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from functools import cmp_to_key
    n=int(input())
    B=[list(map(int,input().split())) for _ in range(n)]
    def cmp(a,b):
        va=min(a[1],b[1]-a[0])
        vb=min(b[1],a[1]-b[0])
        if(va==vb): return 0
        return -1 if(va>vb) else 1
    B.sort(key=cmp_to_key(cmp))
    dp=[-INF]*(30101)
    dp[0]=0
    for i in range(n):
        w,s,v=B[i]
        ndp=dp[:]
        for total in range(20101):
            if(total<=s):
                ndp[total+w]=max(ndp[total+w],dp[total]+v)
        dp=ndp[:]
    print(max(dp[:20101]))
resolve()

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
dp = [0] * 20005
for w, s, v in sorted((map(int, input().split()) for i in xrange(int(input()))) , key = lambda i: i[0] + i[1]):
    for weight in xrange(s, -1, -1):
        dp[weight + w] = max(dp[weight] + v, dp[weight + w])
print max(dp)

Submission status: Accepted

Solution code:
# from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_4
import sys
n=int(input())
blocks=[]
for line in sys.stdin.readlines():
    w,s,v=map(int,line.split())
    blocks.append((w+s,w,s,v))
blocks.sort()

dp=[-1]*20001
dp[0]=0
for _,w,s,v in blocks:
    for i in range(s,-1,-1):
        if dp[i]==-1:
            continue
        dp[i+w]=max(dp[i+w],dp[i]+v)
print(max(dp))

Submission status: Accepted

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

import numpy as np

N = int(input())
WSV = [[int(x) for x in input().split()] for _ in range(N)]

# 上から見てこの順であるとしてよい
WSV.sort(key = lambda x: x[0] + x[1])

# 総重量 -> 価値
dp = np.zeros(2*10**4+100,dtype=np.int64)
for w,s,v in WSV:
    np.maximum(dp[w+s:w-1:-1], dp[s::-1] + v, out=dp[w+s:w-1:-1])

answer = dp.max()
print(answer)

Submission status: Accepted

Solution code:
N=int(raw_input())
TT=[]
for _ in xrange(N):
    w,s,v=list(map(int,raw_input().strip().split(' ')))
    TT+=[(w,s,v)]
TT=sorted(TT,key=lambda X:X[1]+X[0])
dp=[[0]*(2*10**4+1) for i in xrange(N)]
 
#for L in range()
#dp[i][weight]=max(dp[i-1][weight-W[i]]+V[i],dp[i-1][weight]
for i in xrange(N):
    if i==0:
        dp[0][TT[0][0]]=TT[0][2]
        continue
    
    
    for weight in xrange(1,2*10**4+1):
        if TT[i][1]>=weight-TT[i][0] and weight-TT[i][0]>=0:
            dp[i][weight]=max(dp[i-1][weight],dp[i-1][weight-TT[i][0]]+TT[i][2])
        else:
            dp[i][weight]=dp[i-1][weight]
print(max(dp[-1]))

Submission status: Accepted

Solution code:
from collections import Counter

def topological_sort(E, D):
    D = D[:]
    n = len(E)
    Q = [i for i in range(n) if D[i] == 0]
    L = []
    while Q:
        p = Q.pop()
        L.append(p)
        for vf in E[p]:
            D[vf] -= 1
            if not D[vf]:
                Q.append(vf)
    
    if len(L) != n:
        return False
    return L

N = int(input())
wsv = [list(map(int, input().split())) for _ in range(N)]
W, S, V = map(list, zip(*wsv))
 
Edge = [[] for _ in range(N)]
Dim = [0]*N
for i in range(N):
    for j in range(N):
        m1 = min(S[j], S[i]-W[j])
        m2 = min(S[i], S[j]-W[i])
        if m1 == m2:
            continue
        if m1 < m2:
            Edge[i].append(j)
            Dim[j] += 1
        else:
            Edge[j].append(i)
            Dim[i] += 1

L = topological_sort(Edge, Dim)
dp = Counter()
dp[10**9+7] = 0

for l in L[::-1]:
    for k, v in dp.copy().items():
        if k >= W[l]:
            t = min(k - W[l], S[l])
            dp[t] = max(dp[t], v + V[l])

print(max(dp.values()))

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
wsv = [list(map(int, input().split())) for _ in range(N)]
W, S, V = map(list, zip(*wsv))
 
L = sorted(range(N), key = lambda i : W[i]+S[i], reverse = True)

dp = Counter()
dp[10**9+7] = 0

for l in L:
    for k, v in dp.copy().items():
        if k >= W[l]:
            t = min(k - W[l], S[l])
            dp[t] = max(dp[t], v + V[l])
print(max(dp.values()))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n = int(input())
#wsv = [[0,0,0]] + [[int(i) for i in input().split()] for _ in range(n)]
wsv = [[int(i) for i in input().split()] for _ in range(n)]
wsv.sort(key = lambda x: x[0]+x[1]) #sでソート
#print(wsv)

smax = 10000
dp = [0]*(smax*2+1)
for i, (w,s,v) in enumerate(wsv):
    for i in range(s,-1,-1):
        if dp[i] != 0 or i == 0:
                dp[i+w] = max(dp[i+w], dp[i]+v)

print(max(dp))

Submission status: Accepted

Solution code:
import numpy as np


def f(n):
    dp = np.zeros(n * 10 ** 4 + 1, dtype="i8")
    bs = [list(map(int, input().split())) for _ in range(n)]
    bs.sort(key=lambda x: x[0] + x[1])
    for w, s, v in bs:
        np.maximum(dp[w:s + w + 1], dp[:s + 1] + v, out=dp[w:s + w + 1])
    print(np.max(dp))


n = int(input())
f(n)

Submission status: Accepted

Solution code:
def f(n):
    mx = 0
    dp = [0] * (n * 10 ** 4 + 1)
    bs = [list(map(int, input().split())) for _ in range(n)]
    bs.sort(key=lambda x: x[0] + x[1])
    for w, s, v in bs:
        for i in range(w + s, w - 1, -1):
            dpw = dp[i - w] + v
            if dpw > dp[i]:
                dp[i] = dpw
                if dpw > mx:
                    mx = dpw
    print(mx)


n = int(input())
f(n)

Submission status: Accepted

Solution code:
def f(n):
    dp = [0] * (n * 10 ** 4 + 1)
    bs = [list(map(int, input().split())) for _ in range(n)]
    bs.sort(key=lambda x: x[0] + x[1])
    for w, s, v in bs:
        for i in range(w + s, w - 1, -1):
            dpw = dp[i - w] + v
            if dpw > dp[i]:
                dp[i] = dpw
    print(max(dp))


n = int(input())
f(n)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
WSV=[tuple(map(int,input().split())) for i in range(n)]
WSV.sort(key=lambda x:x[0]+x[1])
DP=[0]*(10**4*2+1)
for w,s,v in WSV:
    for i in range(s+1)[::-1]:
        DP[i+w]=max(DP[i+w],DP[i]+v)
print(max(DP))

Submission status: Accepted

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

block.sort(key=lambda x: x[0] + x[1])

dp = [[-float('inf')] * (2*10**4+1) for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for w in range(2 * 10**4 + 1):
        if w <= block[i][1]:
            dp[i+1][w+block[i][0]] = max(dp[i+1][w+block[i][0]], dp[i][w] + block[i][2])
        dp[i+1][w] = max(dp[i+1][w], dp[i][w])

ans = 0
for w in range(2 * 10**4 + 1):
    ans = max(ans, dp[n][w])

print(ans)