白駿7579アプリケーション

質問する

コード#コード#

input = __import__('sys').stdin.readline
n, m = map(int, input().split())
mlist = list(map(int, input().split()))
clist = list(map(int, input().split()))
sum_cost = sum(clist)+1
dp = [[0]*sum_cost for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(sum_cost):
        if clist[i-1] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(mlist[i-1]+dp[i-1][j-clist[i-1]], dp[i-1][j])

for i in range(sum_cost):
    if dp[-1][i] >= m:
        print(i)
        break

に答える

if clist[i-1] > j:
     dp[i][j] = dp[i-1][j]
else:
     dp[i][j] = max(mlist[i-1]+dp[i-1][j-clist[i-1]], dp[i-1][j])