結果

問題 No.703 ゴミ拾い Easy
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:52:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,967 bytes
コンパイル時間 357 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 165,064 KB
最終ジャッジ日時 2025-03-20 18:54:01
合計ジャッジ時間 10,605 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7 WA * 39
権限があれば一括ダウンロードができます

ソースコード

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()))
    
    dq = deque()
    dp_prev = 0  # Represents dp[-1], initially 0
    
    for i in range(n):
        # Current x_i, y_i for j=i
        xi = x[i]
        yi = y[i]
        # The new line for j=i: m = -2*xi, c = xi^2 + yi^2 + dp_prev
        m_new = -2 * xi
        c_new = xi * xi + yi * yi + dp_prev
        
        # Add the new line to the deque, maintaining the order
        while len(dq) >= 2:
            # Last two lines in deque
            m1, c1 = dq[-2]
            m2, c2 = dq[-1]
            # Calculate intersection points
            denom1 = m1 - m2
            if denom1 == 0:
                break
            x1 = (c2 - c1) / denom1  # Intersection of m1 and m2
            denom2 = m2 - m_new
            if denom2 == 0:
                break
            x2 = (c_new - c2) / denom2  # Intersection of m2 and new line
            if x2 <= x1:
                dq.pop()  # Remove the last line as it's dominated
            else:
                break
        dq.append((m_new, c_new))
        
        # Query the minimum value for x = a[i]
        while len(dq) >= 2:
            m1, c1 = dq[0]
            m2, c2 = dq[1]
            # Intersection of first two lines
            denom = m2 - m1
            if denom == 0:
                break
            x_int = (c1 - c2) / denom
            if x_int < a[i]:
                dq.popleft()  # The first line is no longer optimal
            else:
                break
        
        # Get the optimal line and compute current cost
        m_opt, c_opt = dq[0]
        current_cost = m_opt * a[i] + c_opt + a[i] ** 2
        dp_prev = current_cost  # Update for next iteration
    
    print(dp_prev)

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