結果

問題 No.664 超能力者Aと株価予測
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:56:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 74 ms / 4,000 ms
コード長 1,161 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,452 KB
実行使用メモリ 69,564 KB
最終ジャッジ日時 2025-03-20 20:56:23
合計ジャッジ時間 1,524 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

INF = -10**18
dp = [[INF] * (N+1) for _ in range(M+1)]

# Initialize m=0 (no transactions) with initial cash K for all minutes
for i in range(N+1):
    dp[0][i] = K

for m in range(1, M+1):
    for j in range(N+1):
        if dp[m-1][j] == INF:
            continue
        if j >= N:
            continue
        buy_price = A[j]
        current_cash = dp[m-1][j]
        if current_cash < buy_price:
            continue
        s = current_cash // buy_price
        cost = s * buy_price
        remaining = current_cash - cost
        
        for k in range(j+1, N+1):
            sell_price = A[k]
            new_cash = remaining + s * sell_price
            if new_cash > dp[m][k]:
                dp[m][k] = new_cash
    
    # Propagate the maximum cash to subsequent minutes if no transaction is made
    for k in range(1, N+1):
        if dp[m][k] < dp[m][k-1]:
            dp[m][k] = dp[m][k-1]

# Find the maximum cash across all possible transaction counts up to M
max_cash = K
for m in range(M+1):
    if dp[m][N] > max_cash:
        max_cash = dp[m][N]

print(max_cash)
0