結果

問題 No.703 ゴミ拾い Easy
ユーザー gew1fw
提出日時 2025-06-12 20:27:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 301 ms / 1,500 ms
コード長 1,684 bytes
コンパイル時間 158 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 164,968 KB
最終ジャッジ日時 2025-06-12 20:28:27
合計ジャッジ時間 9,836 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

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_prev = 0
    dq = deque()
    
    for i in range(n):
        m_i = -2 * x[i]
        b_i = x[i] ** 2 + y[i] ** 2 + dp_prev
        
        # Add the new line to the deque
        while len(dq) >= 2:
            m1, b1 = dq[-2]
            m2, b2 = dq[-1]
            
            # Compute the intersection between the last two lines and the new line
            # Check if the last line can be removed
            numerator1 = (b2 - b1)
            denominator1 = (m1 - m2)
            numerator2 = (b_i - b2)
            denominator2 = (m2 - m_i)
            
            # Avoid division by cross-multiplying
            lhs = numerator1 * denominator2
            rhs = numerator2 * denominator1
            if denominator1 * denominator2 < 0:
                lhs = -lhs
                rhs = -rhs
            
            if lhs >= rhs:
                dq.pop()
            else:
                break
        
        dq.append((m_i, b_i))
        
        # Query the best line for x = a[i]
        while len(dq) >= 2:
            m0, b0 = dq[0]
            m1, b1 = dq[1]
            val0 = m0 * a[i] + b0
            val1 = m1 * a[i] + b1
            if val0 >= val1:
                dq.popleft()
            else:
                break
        
        best_m, best_b = dq[0]
        dp_i = a[i] ** 2 + (best_m * a[i] + best_b)
        dp_prev = dp_i
    
    print(dp_prev)

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