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: Accepted

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: Accepted

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

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

Submission status: Accepted

Solution code:


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Runtime Error

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]*(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: Runtime Error

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: unsorted_blocks["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: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

N0 = 2**((N+1).bit_length())
INF = 10**18
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = l + N0; R = r + N0
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1; R >>= 1
    while L:
        yield L
        L >>= 1

def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0
        
def update(l, r, x):
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1

    for i in gindex(l, r):
        data[i-1] = max(data[2*i-1], data[2*i]) + lazy[i-1]

def update2(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])

def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])
        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

xs = [0]*(N+1)
ys = [[] for _ in range(N+1)]
for _ in range(M):
    l, r, a = map(int, input().split())
    xs[l] += a
    ys[r].append((l,a))

for i in range(1, N+1):
    update(0,i,xs[i])
    update2(i, query(0, i))
    for l, a in ys[i]:
        update(0, l, -a)
print(query(0,N+1))

Submission status: Runtime Error

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]*1001 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(1001):
        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: Runtime Error

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,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: Runtime Error

Solution code:
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: Runtime Error

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)
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: Runtime Error

Solution code:
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] * 2001
a.sort()
dp[0] = 0
for i in range(n):
  for j in range(2000,-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))