結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:33:54 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,439 bytes |
コンパイル時間 | 232 ms |
コンパイル使用メモリ | 82,516 KB |
実行使用メモリ | 165,212 KB |
最終ジャッジ日時 | 2025-03-31 17:34:48 |
合計ジャッジ時間 | 10,364 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 2 RE * 44 |
ソースコード
import sys import collections 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())) def intersection(a1, m1, a2, m2): # Returns x where a1*x + m1 = a2*x + m2 # a1 != a2 return (m2 - m1) / (a1 - a2) deque = collections.deque() dp_prev = 0 # Initially, dp[-1] = 0 for i in range(n): # Add the line for j = i xi = x[i] yi_sq = y[i] ** 2 new_a = -2 * xi new_m = dp_prev + xi ** 2 + yi_sq # Add the new line to the deque, maintaining the order while len(deque) >= 2: a2, m2 = deque[-1] a1, m1 = deque[-2] x1 = intersection(new_a, new_m, a2, m2) x2 = intersection(a2, m2, a1, m1) if x1 <= x2: deque.pop() else: break deque.append((new_a, new_m)) # Query for the current a[i] k = a[i] while len(deque) >= 2: a1, m1 = deque[0] a2, m2 = deque[1] if a1 * k + m1 >= a2 * k + m2: deque.popleft() else: break best_a, best_m = deque[0] current_min = best_a * k + best_m dp_prev = current_min + k * k print(dp_prev) if __name__ == "__main__": main()