ABC267D - Index × A(Not Continuous ver.)

考え方

dp[i][j]=$i$コ目まで決めて，$j$コ選んだ場合の最大値．

回答例

N, M = map(int, input().split())
A = list(map(int, input().split()))

dp = [[-1<<60] * (M + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for j in range(M):
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (j + 1) * A[i])

print(dp[-1][-1])