結果

問題 No.705 ゴミ拾い Hard
コンテスト
ユーザー qwewe
提出日時 2025-04-24 12:25:44
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,057 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 223,268 KB
最終ジャッジ日時 2025-04-24 12:26:21
合計ジャッジ時間 10,189 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14 WA * 26
権限があれば一括ダウンロードができます

ソースコード

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
    dq = []

    for i in range(n):
        j_max = bisect.bisect_right(x, a[i]) - 1
        if j_max < 0:
            j_max = 0

        best = float('inf')
        for j in range(max(0, j_max - 5), min(i + 1, j_max + 6)):
            cost = (abs(x[j] - a[i]) ** 3) + (y[j] ** 3)
            prev = dp[j-1] if j > 0 else 0
            if prev + cost < best:
                best = prev + cost

        j_min = j_max + 1
        for j in range(max(0, j_min - 5), min(i + 1, j_min + 6)):
            cost = (abs(x[j] - a[i]) ** 3) + (y[j] ** 3)
            prev = dp[j-1] if j > 0 else 0
            if prev + cost < best:
                best = prev + cost

        dp[i] = best

    print(dp[-1])

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