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

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[0], -x[1]))

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

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

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

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] * (10**4+1) for _ in range(n+1)]
for i in range(n):
    wi,si,vi = wsv[i]
    for j in range(1,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: Wrong Answer

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

    print(max(dp[N]))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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 dp[-1]

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


solve()

Submission status: Wrong Answer

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:
      dp[i][sn] = max(dp[i-1][sn],dp[i-1][ss]+v)
print(max(dp[-1]))

Submission status: Wrong Answer

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]*(10**4+1) for _ in range(N+1)]

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

print(max(dp[N]))

Submission status: Wrong Answer

Solution code:
#https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_4


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=[[-1]*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: Wrong Answer

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=[[-1]*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<=(10**4):
                dp[i+1][j+w]=max(dp[i+1][j+w],dp[i][j]+v)
                
    print(max(dp[-1]))
            
        

main()

Submission status: Wrong Answer

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]))
    
    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(10**4+1):
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
            if s>=j and j+w<=(10**4):
                dp[i+1][j+w]=max(dp[i+1][j+w],dp[i][j]+v)
                
    print(max(dp[-1]))
            
        

main()

Submission status: Wrong Answer

Solution code:
#https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_4


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もそこまで．
    ただし，上から積む時に実際には優先度がつくので，重りを適切な基準でソートすべき．
    
    現状，重さが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]))
    
    dp=[[0]*(10**4+1) for _ in range(N+1)]
    
    for i in range(N):
        w,s,v=wsv[i]
        for j in range(10**4+1):
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
            if s>=j and j+w<=(10**4):
                dp[i+1][j+w]=max(dp[i+1][j+w],dp[i][j]+v)
                
    print(max(dp[-1]))
            
        

main()

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 MI(): return map(int, sys.stdin.readline().split())
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],reverse=True)
    m=sum(w for w,s,v in wsv)
    dp=[0]*m
    #print(wsv)
    #print(dp)
    for w,s,v in wsv:
        for j in range(w,m):
            nj=min(j-w,s)
            dp[nj]=max(dp[nj],dp[j]+v)
    #print(dp)
    print(max(dp))

main()

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 MI(): return map(int, sys.stdin.readline().split())
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],reverse=True)
    m=10005
    dp=[0]*m
    #print(wsv)
    #print(dp)
    for w,s,v in wsv:
        for j in range(w,m):
            nj=min(j-w,s)
            dp[nj]=max(dp[nj],dp[j]+v)
    #print(dp)
    print(max(dp))

main()

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 MI(): return map(int, sys.stdin.readline().split())
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],reverse=True)
    m=10005
    dp=[0]*m
    #print(wsv)
    #print(dp)
    for w,s,v in wsv:
        for j in range(w,m):
            nj=min(j-w,s)
            dp[nj]=max(dp[nj],dp[j]+v)
    #print(dp)
    print(dp[0])

main()

Submission status: Wrong Answer

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])
print(max(dp[-1]))

Submission status: Wrong Answer

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])
print(max(dp[-1]))

Submission status: Wrong Answer

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 = cmp_to_key(cmp))
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])
print(max(dp[-1]))

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():
    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]*(20101)
    dp[0]=0
    for i in range(n):
        w,s,v=B[i]
        ndp=dp[:]
        for total in range(10101):
            if(total<=s):
                ndp[total+w]=max(ndp[total+w],dp[total]+v)
        dp=ndp[:]
    print(max(dp[:10101]))
resolve()

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():
    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=10000
    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+w<=maxS):
                ndp[total+w]=max(ndp[total+w],dp[total]+v)
        dp=ndp[:]
    print(max(dp))
resolve()

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():
    from functools import cmp_to_key
    n=int(input())
    W,S,V=[0]*n,[0]*n,[0]*n
    for i in range(n):
        W[i],S[i],V[i]=map(int,input().split())
    ord=list(range(n))
    def cmp(i,j):
        vi=min(S[i],S[j]-W[i])
        vj=min(S[j],S[i]-W[j])
        if(vi==vj): return 0
        return -1 if(vi>vj) else 1
    ord.sort(key=cmp_to_key(cmp))
    maxS=10100
    dp=[-INF]*(maxS+1)
    dp[0]=0
    for i in ord:
        ndp=dp[:]
        for total in range(maxS+1):
            if(total<=S[i] and total+W[i]<=maxS):
                ndp[total+W[i]]=max(ndp[total+W[i]],dp[total]+V[i])
        dp=ndp[:]
    print(max(dp))
resolve()

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():
    from functools import cmp_to_key
    n=int(input())
    W,S,V=[0]*n,[0]*n,[0]*n
    for i in range(n):
        W[i],S[i],V[i]=map(int,input().split())
    ord=list(range(n))
    def cmp(i,j):
        vi=min(S[i],S[j]-W[i])
        vj=min(S[j],S[i]-W[j])
        if(vi==vj): return 0
        return -1 if(vi>vj) else 1
    ord.sort(key=cmp_to_key(cmp))
    maxS=10000
    dp=[-INF]*(maxS+1)
    dp[0]=0
    for i in ord:
        ndp=dp[:]
        for total in range(maxS+1):
            if(total<=S[i] and total+W[i]<=maxS):
                ndp[total+W[i]]=max(ndp[total+W[i]],dp[total]+V[i])
        dp=ndp[:]
    print(max(dp))
resolve()

Submission status: Wrong Answer

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

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.sort(key = lambda x: x[1]+x[0]) #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 i+w <= smax:
            if dp[i] != 0 or i == 0:
                dp[i+w] = max(dp[i+w],dp[i]+v)

print(max(dp))

Submission status: Wrong Answer

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.sort(key = lambda x: x[1]+x[0]) #sでソート
#print(wsv)

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


#    print(dp)

print(max(dp))

Submission status: Wrong Answer

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

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の順にソートすると無駄がない。

Limit=10**4+1

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

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

print(max(DP))

Submission status: Wrong Answer

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の順にソートすると無駄がない。

Limit=10**4+1

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

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

print(max(DP))

Submission status: Wrong Answer

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の順にソートすると無駄がない。

Limit=10**4

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

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

print(max(DP))

Submission status: Wrong Answer

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+1)
#重さの合計がWのときの価値。
#W=10**4ならそれ以上更新されないので、W>=10**4以上のものはそこに置く

for w,s,v in B:
    
    if 10**4-w<=s:
        DP[-1]=max(DP[10**4-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: Wrong Answer

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+1)
#重さの合計がWのときの価値。
#W=10**4ならそれ以上更新されないので、W>=10**4以上のものはそこに置く

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

    if 10**4-w<=s:
        DP[-1]=max(DP[10**4-w:s+1])

print(max(DP))

Submission status: Wrong Answer

Solution code:
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):
  p[j+w]=max(p[j+w],p[j]+v);
  ans=max(ans,p[j+w]);
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
unsorted_blocks = []
for i in range(n):
    w_str, s_str, v_str = input().split(" ")
    w, s, v = int(w_str), int(s_str), int(v_str)
    unsorted_blocks.append({"w": w, "s": s, "v": v})

blocks = sorted(unsorted_blocks, key=lambda block: block["s"]) 

def dp(blocks, max_s):
    max_val = 0
    for i in range(len(blocks)):
        taken =  blocks[i]

        # klo constraint nya
        new_max_s = 0
        if max_s is None:
            new_max_s = taken["s"]
        else:
            new_max_s = min(max_s-taken["w"], taken["s"])

        # ini constraint nya
        if new_max_s < 0:
            continue

        # remaining blocks, taruh sini, biar ga diitung kalau jelas ga mungkin
        remaining_blocks = [blocks[x] for x in range(len(blocks)) if x != i and blocks[x]["w"] <= new_max_s]

        # ini nilai tambahan
        taken_val = taken["v"]
        new_val = taken_val + dp(remaining_blocks, new_max_s)
        if new_val > max_val:
            max_val = new_val

    return max_val

print(dp(blocks, None))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
blocks = []
for i in range(n):
    w_str, s_str, v_str = input().split(" ")
    w, s, v = int(w_str), int(s_str), int(v_str)
    blocks.append({"w": w, "s": s, "v": v})

def dp(blocks, max_s):
    max_val = 0
    for i in range(len(blocks)):
        taken =  blocks[i]

        # klo constraint nya
        new_max_s = 0
        if max_s is None:
            new_max_s = taken["s"]
        else:
            new_max_s = min(max_s-taken["w"], taken["s"])

        # ini constraint nya
        if new_max_s < 0:
            continue

        # remaining blocks, taruh sini, biar ga diitung kalau jelas ga mungkin
        remaining_blocks = [blocks[x] for x in range(len(blocks)) if x != i and blocks[x]["w"] <= new_max_s]

        # ini nilai tambahan
        taken_val = taken["v"]
        new_val = taken_val + dp(remaining_blocks, new_max_s)
        if new_val > max_val:
            max_val = new_val

    return max_val

print(dp(blocks, None))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
blocks = []
for i in range(n):
    w_str, s_str, v_str = input().split(" ")
    w, s, v = int(w_str), int(s_str), int(v_str)
    blocks.append({"w": w, "s": s, "v": v})

blocks = sorted(blocks, key=lambda block: block["s"]) 

def dp(blocks, max_s):
    max_val = 0
    for i in range(len(blocks)):
        taken =  blocks[i]

        # klo constraint nya
        new_max_s = 0
        if max_s is None:
            new_max_s = taken["s"]
        else:
            new_max_s = min(max_s-taken["w"], taken["s"])

        # ini constraint nya
        if new_max_s < 0:
            continue

        # remaining blocks, taruh sini, biar ga diitung kalau jelas ga mungkin
        remaining_blocks = [blocks[x] for x in range(len(blocks)) if x != i]

        # ini nilai tambahan
        taken_val = taken["v"]
        new_val = taken_val + dp(remaining_blocks, new_max_s)
        if new_val > max_val:
            max_val = new_val

    return max_val

print(dp(blocks, None))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
blocks = []
for i in range(n):
    w_str, s_str, v_str = input().split(" ")
    w, s, v = int(w_str), int(s_str), int(v_str)
    blocks.append({"w": w, "s": s, "v": v})

def dp(blocks, max_s):
    max_val = 0
    for i in range(len(blocks)):
        taken =  blocks[i]

        # klo constraint nya
        new_max_s = 0
        if max_s is None:
            new_max_s = taken["s"]
        else:
            new_max_s = min(max_s-taken["w"], taken["s"])

        # ini constraint nya
        if new_max_s < 0:
            continue

        # remaining blocks, taruh sini, biar ga diitung kalau jelas ga mungkin
        remaining_blocks = [blocks[x] for x in range(len(blocks)) if x != i]

        # ini nilai tambahan
        taken_val = taken["v"]
        new_val = taken_val + dp(remaining_blocks, new_max_s)
        if new_val > max_val:
            max_val = new_val

    return max_val

print(dp(blocks, None))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
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], reverse=True)
    m = sum(w for w, s, v in wsv) + 1
    dp = [0] * m
    # print(wsv)
    # print(dp)
    for w, s, v in wsv:
        for j in range(w, m):
            nj = min(j - w, s)
            dp[nj] = max(dp[nj], dp[j] + v)
    # print(dp)
    print(max(dp))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
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], reverse=True)
    dp = {100000000: 0}
    # print(wsv)
    # print(dp)
    for w, s, v in wsv:
        for cap, value in sorted(dp.items()):
            nc = min(cap - w, s)
            if nc<0:continue
            if nc in dp:
                dp[nc] = max(dp[nc], value + v)
            else:
                dp[nc] = value + v
    # print(dp)
    print(max(dp.values()))

main()

Submission status: Time Limit Exceeded

Solution code:
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
#dp[重さの総和]=その重さの総和になる最大価値
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))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(1e7+5))

n = int(raw_input())
w = [0]*n
s = [0]*n
v = [0]*n

for i in range(n):
    w[i], s[i], v[i] = list(map(int, raw_input().split()))
    
a = []
for i in range(n):
    a.append((w[i], s[i], v[i]))



def compare(p, q):
    return p[0]+p[1]-q[0]-q[1]
    # if (p[0]>q[0]):
    #     return 1
    # elif (p[0]<q[0]):
    #     return -1;
    # else:
    #     return p[1]-q[1]

a.sort(cmp=compare)

w = [x[0] for x in a]
s = [x[1] for x in a]
v = [x[2] for x in a]

dp = [[-1]*(10000+1) for i in range(1000+1)]

def solve(i, wsum):
    if (i==n):
        return 0
    if wsum>1e4:
        return 0
    
    if (dp[i][wsum]!=-1):
        return dp[i][wsum]

    ans = 0

    if s[i]>=wsum:
        ans = max(ans, v[i]+solve(i+1, wsum+w[i]))
        ans = max(ans, solve(i+1, wsum))
    else:
        ans = max(ans, solve(i+1, wsum))

    dp[i][wsum]=ans
    return ans

print(solve(0, 0))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
TT=[]
for _ in range(N):
    w,s,v=list(map(int,input().strip().split(' ')))
    TT+=[(w,s,v)]
TT=sorted(TT,key=lambda X:X[1]+X[0])
dp=[[0]*(10**4+1) for i in range(N)]

#for L in range()
#dp[i][weight]=max(dp[i-1][weight-W[i]]+V[i],dp[i-1][weight]
for i in range(N):
    if i==0:
        dp[0][TT[0][0]]=TT[0][2]
        continue
    
    
    for weight in range(1,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: Time Limit Exceeded

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, dpv in enumerate(dp[s::-1]):
            nv = dpv + v
            ni = s + w - i
            if nv > dp[ni]:
                dp[ni] = nv
                if nv > mx:
                    mx = nv
    print(mx)


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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
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))