結果

問題 No.703 ゴミ拾い Easy
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:33:54
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,439 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 165,212 KB
最終ジャッジ日時 2025-03-31 17:34:48
合計ジャッジ時間 10,364 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 RE * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import collections

def main():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    x = list(map(int, sys.stdin.readline().split()))
    y = list(map(int, sys.stdin.readline().split()))

    def intersection(a1, m1, a2, m2):
        # Returns x where a1*x + m1 = a2*x + m2
        # a1 != a2
        return (m2 - m1) / (a1 - a2)

    deque = collections.deque()
    dp_prev = 0  # Initially, dp[-1] = 0

    for i in range(n):
        # Add the line for j = i
        xi = x[i]
        yi_sq = y[i] ** 2
        new_a = -2 * xi
        new_m = dp_prev + xi ** 2 + yi_sq

        # Add the new line to the deque, maintaining the order
        while len(deque) >= 2:
            a2, m2 = deque[-1]
            a1, m1 = deque[-2]
            x1 = intersection(new_a, new_m, a2, m2)
            x2 = intersection(a2, m2, a1, m1)
            if x1 <= x2:
                deque.pop()
            else:
                break
        deque.append((new_a, new_m))

        # Query for the current a[i]
        k = a[i]
        while len(deque) >= 2:
            a1, m1 = deque[0]
            a2, m2 = deque[1]
            if a1 * k + m1 >= a2 * k + m2:
                deque.popleft()
            else:
                break
        best_a, best_m = deque[0]
        current_min = best_a * k + best_m

        dp_prev = current_min + k * k

    print(dp_prev)

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