結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:19:21 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,499 bytes |
コンパイル時間 | 196 ms |
コンパイル使用メモリ | 82,232 KB |
実行使用メモリ | 164,948 KB |
最終ジャッジ日時 | 2025-04-15 23:20:49 |
合計ジャッジ時間 | 8,953 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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) for i in range(1, n + 1): dp[i] = float('inf') dq = deque() if n > 0: dq.append((-2 * x[0], dp[0] + x[0]**2 + y[0]**2)) for i in range(n): current_a = a[i] # Query processing while len(dq) >= 2: m1, b1 = dq[0] m2, b2 = dq[1] if (b2 - b1) <= current_a * (m1 - m2): dq.popleft() else: break if dq: m, b = dq[0] min_val = m * current_a + b dp[i+1] = current_a * current_a + min_val # Add the next line if there is a next garbage if i + 1 < n: new_m = -2 * x[i+1] new_b = dp[i+1] + x[i+1]**2 + y[i+1]**2 # Maintain the deque while len(dq) >= 2: m1, b1 = dq[-2] m2, b2 = dq[-1] denom1 = m1 - m2 denom2 = m2 - new_m x1 = (b2 - b1) / denom1 x2 = (new_b - b2) / denom2 if x1 >= x2: dq.pop() else: break dq.append((new_m, new_b)) print(dp[n]) if __name__ == "__main__": main()