結果

問題 No.705 ゴミ拾い Hard
ユーザー qwewe
提出日時 2025-05-14 12:47:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 928 bytes
コンパイル時間 341 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 223,384 KB
最終ジャッジ日時 2025-05-14 12:47:56
合計ジャッジ時間 10,373 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 15 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    idx += 1
    a = list(map(int, data[idx:idx+n]))
    idx += n
    x = list(map(int, data[idx:idx+n]))
    idx += n
    y = list(map(int, data[idx:idx+n]))
    idx += n
    
    dp = [0] * (n + 1)
    for k in range(n):
        current_a = a[k]
        # Find the largest j where x[j] <= current_a
        m = bisect.bisect_right(x, current_a) - 1
        # Expand the candidate range around m
        start = max(0, m - 20)
        end = min(k, m + 20)
        min_cost = float('inf')
        for j in range(start, end + 1):
            if j > k:
                continue
            cost = dp[j] + abs(x[j] - current_a) ** 3 + (y[j] ** 3)
            if cost < min_cost:
                min_cost = cost
        dp[k + 1] = min_cost
    
    print(dp[n])

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