結果
問題 |
No.703 ゴミ拾い Easy
|
ユーザー |
|
提出日時 | 2022-03-10 00:11:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 313 ms / 1,500 ms |
コード長 | 819 bytes |
コンパイル時間 | 429 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 166,984 KB |
最終ジャッジ日時 | 2024-09-14 01:38:35 |
合計ジャッジ時間 | 11,558 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 46 |
ソースコード
from collections import deque deq = deque() def check(f1, f2, f3): return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0]) def f(f1, x): return f1[0]*x + f1[1] # add f_i(x) = a*x + b def add_line(a, b): f1 = (a, b) while len(deq) >= 2 and check(deq[-2], deq[-1], f1): deq.pop() deq.append(f1) # min f_i(x) def query(x): while len(deq) >= 2 and f(deq[0], x) >= f(deq[1], x): deq.popleft() return f(deq[0], x) n = int(input()) a = list(map(int,input().split())) x = list(map(int,input().split())) y = list(map(int,input().split())) dp = [0] * n add_line(-2 * x[0],x[0] ** 2 + y[0] ** 2) for i in range(n): tmp = query(a[i]) dp[i] = tmp + a[i] ** 2 if i < n - 1: add_line(-2 * x[i+1],dp[i] + x[i+1] ** 2 + y[i+1] ** 2) print(dp[-1])