結果

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

ソースコード

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()
    
    for i in range(n):
        if i == 0:
            prev_dp = 0
        else:
            prev_dp = dp[i-1]
        
        xi = x[i]
        yi = y[i]
        Ci = prev_dp + xi * xi + yi * yi
        mi = -2 * xi
        
        while len(dq) >= 2:
            l_prev = dq[-2]
            l_last = dq[-1]
            numerator1 = l_last[1] - Ci
            denominator1 = mi - l_last[0]
            
            if denominator1 == 0:
                if Ci < l_last[1]:
                    dq.pop()
                else:
                    break
                continue
            
            a1 = numerator1 / denominator1
            numerator2 = l_prev[1] - l_last[1]
            denominator2 = l_last[0] - l_prev[0]
            
            if denominator2 == 0:
                if l_last[1] > l_prev[1]:
                    dq.pop()
                else:
                    break
                continue
            
            a2 = numerator2 / denominator2
            
            if a1 < a2:
                dq.pop()
            else:
                break
        
        dq.append((mi, Ci))
        
        ai = a[i]
        while len(dq) >= 2:
            l1 = dq[0]
            l2 = dq[1]
            numerator = l2[1] - l1[1]
            denominator = l1[0] - l2[0]
            
            if denominator == 0:
                if l1[0] * ai + l1[1] <= l2[0] * ai + l2[1]:
                    break
                else:
                    dq.popleft()
                continue
            
            a_intersect = numerator / denominator
            if a_intersect <= ai:
                dq.popleft()
            else:
                break
        
        l = dq[0]
        min_val = l[0] * ai + l[1]
        dp[i] = ai * ai + min_val
    
    print(dp[-1])

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