結果

問題 No.664 超能力者Aと株価予測
ユーザー titiatitia
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
53,248 KB
testcase_01 AC 38 ms
52,992 KB
testcase_02 AC 50 ms
62,336 KB
testcase_03 AC 41 ms
52,352 KB
testcase_04 AC 43 ms
52,608 KB
testcase_05 AC 38 ms
52,480 KB
testcase_06 AC 92 ms
76,160 KB
testcase_07 AC 81 ms
76,108 KB
testcase_08 AC 443 ms
79,472 KB
testcase_09 AC 73 ms
74,240 KB
testcase_10 AC 999 ms
84,484 KB
testcase_11 AC 1,800 ms
109,184 KB
testcase_12 AC 1,341 ms
97,192 KB
testcase_13 AC 173 ms
77,540 KB
testcase_14 AC 37 ms
52,736 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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