B - IOI饅頭(IOI Manju)
]] := 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)