結果

問題 No.703 ゴミ拾い Easy
ユーザー gew1fw
提出日時 2025-06-12 16:48:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,022 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 82,056 KB
実行使用メモリ 164,664 KB
最終ジャッジ日時 2025-06-12 16:49:35
合計ジャッジ時間 11,605 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26 WA * 20
権限があれば一括ダウンロードができます

ソースコード

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()
    prev_dp = 0  # dp[-1] is 0
    
    for i in range(n):
        xi = x[i]
        yi = y[i]
        ai = a[i]
        
        Ci = prev_dp + xi**2 + yi**2
        mi = -2 * xi
        bi = Ci
        
        # Add the new line to the deque
        while len(dq) >= 2:
            l1 = dq[-2]
            l2 = dq[-1]
            
            # Compute intersection of l1 and l2
            numerator = l2[1] - l1[1]
            denominator = l1[0] - l2[0]
            if denominator == 0:
                x12 = float('inf')
            else:
                x12 = numerator / denominator
            
            # Compute intersection of new line and l2
            numerator_new = bi - l2[1]
            denominator_new = l2[0] - mi
            if denominator_new == 0:
                x_new = float('inf')
            else:
                x_new = numerator_new / denominator_new
            
            if x_new <= x12:
                dq.pop()
            else:
                break
        dq.append((mi, bi))
        
        # Query for ai, remove lines not needed
        while len(dq) >= 2:
            l0 = dq[0]
            l1 = dq[1]
            
            numerator = l1[1] - l0[1]
            denominator = l0[0] - l1[0]
            if denominator == 0:
                x01 = float('inf')
            else:
                x01 = numerator / denominator
            
            if x01 <= ai:
                dq.popleft()
            else:
                break
        
        # Get the minimal value
        m, b = dq[0]
        min_val = m * ai + b
        
        dp_i = ai**2 + min_val
        
        # Update prev_dp for next iteration
        prev_dp = dp_i
    
    print(prev_dp)

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