結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:24:37 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,261 bytes |
コンパイル時間 | 277 ms |
コンパイル使用メモリ | 82,288 KB |
実行使用メモリ | 165,024 KB |
最終ジャッジ日時 | 2025-04-15 23:26:03 |
合計ジャッジ時間 | 7,866 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 2 RE * 44 |
ソースコード
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 + 1) q = deque() for i in range(n): # Add the line for j = i m_i = -2 * x[i] b_i = dp[i] + x[i] ** 2 + y[i] ** 2 # Maintain the deque for convex hull while len(q) >= 2: m1, b1 = q[-2] m2, b2 = q[-1] # Calculate intersection points x1 = (b2 - b1) / (m1 - m2) x2 = (b_i - b2) / (m2 - m_i) if x2 <= x1: q.pop() else: break q.append((m_i, b_i)) # Compute dp[i+1] current_a = a[i] # Find the optimal line in the deque while len(q) >= 2: m1, b1 = q[0] m2, b2 = q[1] if (b2 - b1) / (m1 - m2) <= current_a: q.popleft() else: break m, b = q[0] min_val = m * current_a + b dp[i + 1] = current_a ** 2 + min_val print(dp[n]) if __name__ == "__main__": main()