結果

問題 No.595 登山
ユーザー qwewe
提出日時 2025-05-14 13:26:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 139 ms / 1,500 ms
コード長 2,959 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 112,512 KB
最終ジャッジ日時 2025-05-14 13:27:40
合計ジャッジ時間 4,255 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    N, P = map(int, sys.stdin.readline().split())
    H = list(map(int, sys.stdin.readline().split()))

    if N == 1:
        print(0)
        return

    # D_fwd[m] = cost to move from H[m] to H[m+1]
    D_fwd = [0] * (N - 1)
    for m in range(N - 1):
        D_fwd[m] = max(0, H[m+1] - H[m])

    # PD_fwd[x] = sum of D_fwd[0]...D_fwd[x-1]
    # PD_fwd[k] = cost to walk H[0] -> H[1] -> ... -> H[k]
    PD_fwd = [0] * N 
    current_sum_fwd = 0
    # PD_fwd[0] = 0 (cost to walk H[0] -> H[0])
    for x in range(N - 1): 
        current_sum_fwd += D_fwd[x]
        PD_fwd[x+1] = current_sum_fwd
    
    # D_rev[m] = cost to move from H[m+1] to H[m]
    D_rev = [0] * (N - 1)
    for m in range(N - 1):
        D_rev[m] = max(0, H[m] - H[m+1])
    
    # PD_rev[k] = cost to walk H[k] -> H[k-1] -> ... -> H[0]
    PD_rev = [0] * N
    current_sum_rev = 0
    # PD_rev[0] = 0 (cost H[0] -> H[0])
    for x in range(N - 1): 
        current_sum_rev += D_rev[x] # D_rev[x] is cost H[x+1] -> H[x]
        PD_rev[x+1] = current_sum_rev
    
    # dp[k] = min cost to cover H[0]...H[k-1] (first k locations)
    dp = [0] * (N + 1) # dp[0] to dp[N]

    dp[1] = 0 # Cost to cover H[0] (first location) is 0 as we start there.
    
    # min_term_fwd will store min(dp[x] - PD_fwd[x]) for x from 1 up to current k-1.
    # min_term_rev will store min(dp[x] - PD_rev[x]) for x from 1 up to current k-1.
    # Initialize with x=1 values.
    # PD_fwd[1] is cost H[0]->H[1].
    # PD_rev[1] is cost H[1]->H[0].
    min_term_fwd = dp[1] - PD_fwd[1] 
    min_term_rev = dp[1] - PD_rev[1] 

    for k in range(2, N + 1):
        # Option 1: Walk H[0] -> ... -> H[k-1] in one segment
        # Cost is sum D_fwd[0]...D_fwd[k-2], which is PD_fwd[k-1].
        val_one_segment_fwd = PD_fwd[k-1]
        
        # Option 2a: Split. Last segment H[j_idx]...H[k-1] walked H[j_idx]->H[k-1].
        # Here, j_idx is the 0-based index. dp[j] covers first j locations H[0]...H[j-1].
        # New segment from H[j] to H[k-1].
        # cost dp[j] + P + (PD_fwd[k-1] - PD_fwd[j])
        # This is P + PD_fwd[k-1] + (dp[j] - PD_fwd[j])
        # where j loops from 1 to k-1. min_term_fwd stores min(dp[j] - PD_fwd[j])
        term_A = P + PD_fwd[k-1] + min_term_fwd
        
        # Option 2b: Split. Last segment H[j_idx]...H[k-1] walked H[k-1]->H[j_idx].
        # cost dp[j] + P + (PD_rev[k-1] - PD_rev[j])
        # This is P + PD_rev[k-1] + (dp[j] - PD_rev[j])
        term_B = P + PD_rev[k-1] + min_term_rev
        
        dp[k] = min(val_one_segment_fwd, term_A, term_B)
        
        # Update min_terms for next iteration (for k+1, this k will be part of j range)
        # dp[k] refers to covering first k locations. PD_fwd[k] is cost H[0]...H[k].
        if k < N : 
             min_term_fwd = min(min_term_fwd, dp[k] - PD_fwd[k])
             min_term_rev = min(min_term_rev, dp[k] - PD_rev[k])
             
    print(dp[N])

solve()
0