結果

問題 No.595 登山
ユーザー gew1fw
提出日時 2025-06-12 20:01:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,118 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,008 KB
実行使用メモリ 121,656 KB
最終ジャッジ日時 2025-06-12 20:04:40
合計ジャッジ時間 4,424 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    P = int(input[1])
    H = list(map(int, input[2:2+N]))
    
    if P == 0:
        print(0)
        return
    
    # 计算sum_diff
    sum_diff = 0
    for i in range(N-1):
        diff = H[i+1] - H[i]
        if diff > 0:
            sum_diff += diff
    
    # 计算sum_forward数组
    sum_forward = [0] * (N + 1)
    current = 0
    for k in range(2, N + 1):
        i = k - 2
        diff = H[i+1] - H[i]
        current += max(0, diff)
        sum_forward[k] = current
    
    # 计算sum_backward数组
    sum_backward = [0] * (N + 2)  # 多分配一个空间，避免越界
    for k in range(N-1, 0, -1):
        i = k - 1
        diff = H[i] - H[i+1]
        sum_backward[k] = sum_backward[k+1] + max(0, diff)
    
    # 找到min_sum
    min_sum = float('inf')
    for k in range(1, N+1):
        s = sum_forward[k] + sum_backward[k]
        if s < min_sum:
            min_sum = s
    
    candidate2 = P + min_sum
    result = min(sum_diff, candidate2)
    print(result)

if __name__ == '__main__':
    main()
0