提出 #44967001

---

ソースコード 拡げる

N = int(input())
costs = []
sz = 0
for _ in range(N):
    X, Y, Z = map(int, input().split())
    sz += Z
    costs.append((Z, max(0, (Y+X+1)//2 - X)))

z2 = (sz+1)//2

INF = 10**18
dp = [[INF]*(N+1) for _ in range(z2+1)]
dp[0][0] = 0
for k, (dx, z) in enumerate(costs):
    for i in range(z2 + 1):
        # 使う場合
        if i + dx <= z2:
            dp[i + dx][k+1] = min(dp[i + dx][k+1], dp[i][k] + z)
        else:
            dp[z2][k+1] = min(dp[z2][k+1], dp[i][k] + z)
        dp[i][k+1] = min(dp[i][k+1], dp[i][k])

print(dp[z2][N])

提出情報

ジャッジ結果