結果

問題 No.664 超能力者Aと株価予測
コンテスト
ユーザー titia
提出日時 2024-08-17 06:56:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,800 ms / 4,000 ms
コード長 959 bytes
コンパイル時間 474 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 109,184 KB
最終ジャッジ日時 2024-08-17 06:56:55
合計ジャッジ時間 6,580 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

from operator import itemgetter

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

DP=[[] for i in range(M+1)]
DP[0].append([0,K])
for a in A:
    NDP=[[] for i in range(M+1)]

    for i in range(M+1):
        for x,k in DP[i]:
            NDP[i].append([x,k])

    for i in range(M+1):
        for x,k in DP[i]:
            plus=k//a

            NDP[i].append([x+plus,k-plus*a])

            if i+1<=M:
                NDP[i+1].append([0,k+x*a])

    DP=[[] for i in range(M+1)]

    for i in range(M+1):
        NDP[i].sort(key=itemgetter(1),reverse=True)
        NDP[i].sort(key=itemgetter(0))

        for j in range(len(NDP[i])):
            if j>=1 and NDP[i][j][0]==NDP[i][j-1][0] and NDP[i][j][1]<=NDP[i][j-1][1]:
                continue

            x,k=NDP[i][j]

            DP[i].append([x,k])


ANS=0

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

print(ANS)
0