結果

問題 No.664 超能力者Aと株価予測
コンテスト
ユーザー titia
提出日時 2024-08-17 06:37:31
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 719 bytes
コンパイル時間 421 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 79,360 KB
最終ジャッジ日時 2024-08-17 06:37:42
合計ジャッジ時間 9,229 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 RE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

N,M,K=map(int,input().split())
A=[int(input()) for i in range(N+1)]

DP=[[-1<<30]*1000 for i in range(M+1)]
DP[0][0]=K

for a in A:
    NDP=[[-1<<30]*1000 for i in range(M+1)]

    for i in range(M+1):
        for j in range(1000):
            if DP[i][j]<0:
                continue

            now=DP[i][j]

            NDP[i][j]=max(NDP[i][j],now)

            for k in range(now//a+1):
                NDP[i][j+k]=max(NDP[i][j+k],now-a*k)

            for k in range(j+1):
                if i+1<=M:
                    NDP[i+1][j-k]=max(NDP[i+1][j-k],now+a*k)

    DP=NDP

ANS=0

for i in range(M+1):
    for j in range(500):
        ANS=max(ANS,DP[i][j])

print(ANS)
0