結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:19:16 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,772 bytes |
コンパイル時間 | 355 ms |
コンパイル使用メモリ | 81,532 KB |
実行使用メモリ | 164,588 KB |
最終ジャッジ日時 | 2025-04-15 23:21:00 |
合計ジャッジ時間 | 9,846 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 21 WA * 25 |
ソースコード
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() # Function to add a line (m, b) to the deque def add_line(m, b): while len(dq) >= 2: m1, b1 = dq[-2] m2, b2 = dq[-1] # Calculate intersection x between new line and last line in deque if m == m2: x1 = float('-inf') else: x1 = (b2 - b) / (m - m2) # Calculate intersection x between last two lines in deque if m1 == m2: x2 = float('-inf') else: x2 = (b2 - b1) / (m1 - m2) if x1 <= x2: dq.pop() else: break dq.append((m, b)) # Function to query the minimum value at x_coord def query(x_coord): while len(dq) >= 2: m1, b1 = dq[0] m2, b2 = dq[1] if m1 * x_coord + b1 > m2 * x_coord + b2: dq.popleft() else: break m, b = dq[0] return m * x_coord + b # Initialize for i=0 m0 = -2 * x[0] b0 = 0 + x[0]**2 + y[0]**2 # dp[-1] is considered 0 add_line(m0, b0) dp[0] = a[0]**2 + query(a[0]) for i in range(1, n): # Add the line for j=i mi = -2 * x[i] bi = dp[i-1] + x[i]**2 + y[i]**2 add_line(mi, bi) # Query the minimum value for a[i] min_val = query(a[i]) dp[i] = a[i]**2 + min_val print(dp[-1]) if __name__ == "__main__": main()