結果

問題 No.703 ゴミ拾い Easy
ユーザー gew1fw
提出日時 2025-06-12 20:25:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 324 ms / 1,500 ms
コード長 1,789 bytes
コンパイル時間 186 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 164,964 KB
最終ジャッジ日時 2025-06-12 20:25:43
合計ジャッジ時間 10,186 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()))
    
    s = [x[i] ** 2 + y[i] ** 2 for i in range(n)]
    
    dp = [0] * n
    deq = deque()
    
    for i in range(n):
        # Calculate m_j for j = i
        if i == 0:
            m_j = s[i]
        else:
            m_j = dp[i-1] + s[i]
        current_slope = -2 * x[i]
        current_intercept = m_j
        
        # Add the new line to the deque, maintaining convex hull
        while len(deq) >= 2:
            # Last two lines in deque
            l1_slope, l1_intercept = deq[-1]
            l2_slope, l2_intercept = deq[-2]
            
            # Check if the last line can be removed
            left = (current_intercept - l2_intercept) * (l2_slope - l1_slope)
            right = (l1_intercept - l2_intercept) * (l2_slope - current_slope)
            if left <= right:
                deq.pop()
            else:
                break
        deq.append((current_slope, current_intercept))
        
        # Query the best line for current a[i]
        while len(deq) >= 2:
            # Compare first two lines
            l0_slope, l0_intercept = deq[0]
            l1_slope, l1_intercept = deq[1]
            
            val0 = l0_slope * a[i] + l0_intercept
            val1 = l1_slope * a[i] + l1_intercept
            if val0 >= val1:
                deq.popleft()
            else:
                break
        
        best_slope, best_intercept = deq[0]
        min_val = best_slope * a[i] + best_intercept
        dp[i] = a[i] ** 2 + min_val
    
    print(dp[-1])

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