PythonでJOI難易度6を埋める #23

B - IOI饅頭(IOI Manju)

 dp[ i ] [ j ] := i番目の箱まで使えるときの,j個以上の饅頭を入れるために必要な金額の最小として,dpします.饅頭は高い方から売った方がいいので,降順でsortして,累積和を取っておきます.

from sys import stdin
input = stdin.readline
inf = float('inf')

m, n = map(int, input().strip().split())
manjuu = [int(input().strip()) for _ in range(m)]
boxes = [list(map(int, input().strip().split())) for _ in range(n)]

manjuu.sort(reverse = True)
csum_price = [0]
for i in range(m):
    csum_price.append(csum_price[-1] + manjuu[i])

ans = 0
dp = [[inf for _ in range(m + 1)] for _ in range(n)]
for i in range(n):
    dp[i][0] = 0

for i in range(1, m + 1):
    if i > boxes[0][0]:
        break
    dp[0][i] = boxes[0][1]
    ans = max(csum_price[i] - dp[0][i], ans)

cnt = boxes[0][0]
for i in range(1, n):
    cnt += boxes[i][0]
    for j in range(m + 1):
        if j <= cnt:
            dp[i][j] = min(dp[i - 1][max(j - boxes[i][0], 0)] + boxes[i][1], dp[i - 1][j], dp[i][j])

            ans = max(csum_price[j] - dp[i][j], ans)
print(ans)