結果

問題 No.703 ゴミ拾い Easy
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:19:16
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,772 bytes
コンパイル時間 355 ms
コンパイル使用メモリ 81,532 KB
実行使用メモリ 164,588 KB
最終ジャッジ日時 2025-04-15 23:21:00
合計ジャッジ時間 9,846 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

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()))
    
    dp = [0] * n
    dq = deque()
    
    # Function to add a line (m, b) to the deque
    def add_line(m, b):
        while len(dq) >= 2:
            m1, b1 = dq[-2]
            m2, b2 = dq[-1]
            # Calculate intersection x between new line and last line in deque
            if m == m2:
                x1 = float('-inf')
            else:
                x1 = (b2 - b) / (m - m2)
            # Calculate intersection x between last two lines in deque
            if m1 == m2:
                x2 = float('-inf')
            else:
                x2 = (b2 - b1) / (m1 - m2)
            if x1 <= x2:
                dq.pop()
            else:
                break
        dq.append((m, b))
    
    # Function to query the minimum value at x_coord
    def query(x_coord):
        while len(dq) >= 2:
            m1, b1 = dq[0]
            m2, b2 = dq[1]
            if m1 * x_coord + b1 > m2 * x_coord + b2:
                dq.popleft()
            else:
                break
        m, b = dq[0]
        return m * x_coord + b
    
    # Initialize for i=0
    m0 = -2 * x[0]
    b0 = 0 + x[0]**2 + y[0]**2  # dp[-1] is considered 0
    add_line(m0, b0)
    dp[0] = a[0]**2 + query(a[0])
    
    for i in range(1, n):
        # Add the line for j=i
        mi = -2 * x[i]
        bi = dp[i-1] + x[i]**2 + y[i]**2
        add_line(mi, bi)
        # Query the minimum value for a[i]
        min_val = query(a[i])
        dp[i] = a[i]**2 + min_val
    
    print(dp[-1])

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