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.

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





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






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


def DD(arg): return defaultdict(arg)


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


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


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


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


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


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


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


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


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]


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





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

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

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

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

Solution (Python):

def resolve():
    from functools import cmp_to_key
    
    
    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 = [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)]
    
    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()

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

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

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

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

Solution (Python):


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

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

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

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

Solution (Python):

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
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])

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

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

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

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

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

    for i in range(y+1):
        i = y-i
        dp[i+x] = max(dp[i+x], dp[i]+z)

print(max(dp))

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

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

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)

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

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

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

Solution (Python):
I = [int(_) for _ in open(0).read().split()]
N = I[0]
W, S, V = I[1::3], I[2::3], I[3::3]
dp = [-float('inf')] * (2 * 10**4 + 5)
dp[0] = 0

for s, w, v in sorted(zip(S, W, V), key=lambda swv: swv[0] + swv[1]):
    for wbefore in range(s, -1, -1):
        dp[wbefore + w] = max(dp[wbefore + w], dp[wbefore] + v)
print(max(dp))

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

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

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

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

Solution (Python):

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

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

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

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

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

Solution (Python):



n = int(input())

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


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

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

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

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

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

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

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


DP=[0]*(10**4+2)



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

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


DP=[0]*(10**4+2)



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

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

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

print(max(DP))

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


DP=[0]*(10**4+2)



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

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

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

print(max(DP))

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


DP=[0]*(10**4+2)



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

Solution (Python):


n = input()
items = []
mw = 0
ms = 0
for _ in range(n):
    w, s, v = map(int, raw_input().split())
    items.append((-(s + w), s, w, v))
    ms = max(ms, s)
    mw = max(mw, w)
items.sort()

dp = [[0] * (mw + ms + 1) for _ in range(n)]
for i in range(items[n - 1][2], ms + mw + 1):
    dp[n - 1][i] = items[n - 1][3]
for i in range(n - 2, -1, -1):
    _, s, w, v = items[i]
    for j in range(1, mw + ms + 1):
        dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        if 0 <= j - w <= s:
            dp[i][j] = max(dp[i][j], v + dp[i + 1][j - w])
print(max(dp[0]))

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

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

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

Solution (Python):
N = int(input())
P = [list(map(int, input().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, -1, -1):
        dp[i+w] = max(dp[i+w], dp[i] + v)
print(max(dp))

Solution (Python):
n = int(input())
a = []
for i in range(n):
  x,y,z = map(int,input().split())
  a.append([x+y,x,y,z])
dp = [-1] * 20001
a.sort()
dp[0] = 0
for i in range(n):
  for j in range(20000,-1,-1):
    if dp[j] != -1 and a[i][2]>= j:
      dp[j+a[i][1]] = max(dp[j+a[i][1]],dp[j]+a[i][3])
print(max(dp))

Solution (Python):
p=[0]*6**6
for w,s,v in sorted([list(map(int,input().split()))for _ in[0]*int(input())],key=lambda a:a[0]+a[1]):
 for j in range(s,-1,-1):p[j+w]=max(p[j+w],p[j]+v)
print(max(p))

Solution (Python):
n=int(input());
ans=0;
p=[0]*22222;
for w,s,v in sorted([list(map(int,input().split()))for _ in[0]*n],key=lambda a:a[0]+a[1]):
 for j in range(s,-1,-1):
  p[j+w]=max(p[j+w],p[j]+v);
  ans=max(ans,p[j+w]);
print(ans)