結果

問題 No.1077 Noelちゃんと星々4
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:45:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,736 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,548 KB
実行使用メモリ 77,492 KB
最終ジャッジ日時 2025-03-20 20:45:28
合計ジャッジ時間 2,106 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n = int(input())
Y = list(map(int, input().split()))

if n == 0:
    print(0)
    exit()

current_candidates = {}

start = max(0, Y[0] - 1000)
end = Y[0] + 1000
for v in range(start, end + 1):
    cost = abs(Y[0] - v)
    current_candidates[v] = cost

prev_sorted = sorted(current_candidates.keys())

for i in range(1, n):
    # Prepare min_prefix using prev_sorted
    min_prefix = {}
    min_so_far = float('inf')
    for v in prev_sorted:
        if current_candidates[v] < min_so_far:
            min_so_far = current_candidates[v]
        min_prefix[v] = min_so_far

    new_candidates = {}
    yi = Y[i]
    # Determine the search range for current v_i
    if prev_sorted:
        lower_bound = prev_sorted[0]
    else:
        break  # should not happen as n >=1
    start_i = max(lower_bound, yi - 1000)
    end_i = yi + 1000

    # Iterate possible v_i in the range, using step 1 for integer v_i
    for v_i in range(start_i, end_i + 1):
        # Find the largest v_prev <= v_i using binary search on prev_sorted
        idx = bisect.bisect_right(prev_sorted, v_i) - 1
        if idx < 0:
            continue  # no valid v_prev <= v_i
        best_v_prev = prev_sorted[idx]
        current_min = min_prefix[best_v_prev]
        cost = current_min + abs(yi - v_i)
        # Update new_candidates
        if v_i not in new_candidates or cost < new_candidates[v_i]:
            new_candidates[v_i] = cost

    # Update for next iteration
    current_candidates = new_candidates
    if not current_candidates:
        break  # no possible sequence, though problem states n>=1
    prev_sorted = sorted(current_candidates.keys())

if current_candidates:
    print(min(current_candidates.values()))
else:
    print(0)
0