結果

問題 No.664 超能力者Aと株価予測
ユーザー titiatitia
提出日時 2024-08-17 06:09:57
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 716 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 78,592 KB
最終ジャッジ日時 2024-08-17 06:10:02
合計ジャッジ時間 4,602 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 55 ms
65,152 KB
testcase_01 AC 58 ms
66,432 KB
testcase_02 AC 63 ms
69,376 KB
testcase_03 AC 39 ms
59,136 KB
testcase_04 AC 42 ms
58,880 KB
testcase_05 AC 44 ms
57,728 KB
testcase_06 AC 206 ms
75,904 KB
testcase_07 AC 84 ms
75,776 KB
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 AC 122 ms
76,624 KB
testcase_14 AC 55 ms
60,032 KB
権限があれば一括ダウンロードができます

ソースコード

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]*500 for i in range(M+1)]
DP[0][0]=K

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

    for i in range(M+1):
        for j in range(500):
            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