#[allow(dead_code)] fn getline() -> String { let mut res = String::new(); std::io::stdin().read_line(&mut res).ok(); res } #[allow(unused_macros)] macro_rules! readl { ($t: ty) => { { let s = getline(); s.trim().parse::<$t>().unwrap() } }; ($( $t: ty),+ ) => { { let s = getline(); let mut iter = s.trim().split(' '); ($(iter.next().unwrap().parse::<$t>().unwrap(),)*) } }; } #[allow(unused_macros)] macro_rules! readlvec { ($t:ty) => {{ let s = getline(); let iter = s.trim().split(' '); iter.map(|x| x.parse().unwrap()).collect::>() }}; } #[allow(unused_macros)] macro_rules! debug { ($x:expr) => { println!("{}: {:?}", stringify!($x), $x) }; } // macro_rules! debug { ($x: expr) => () } #[allow(dead_code)] fn show(iter: T) -> String where T: Iterator, T::Item: std::fmt::Display, { let mut res = iter.fold(String::new(), |sum, e| sum + &format!("{} ", e)); res.pop(); res } #[allow(unused_imports)] use std::cmp::{max, min}; #[allow(unused_imports)] use std::collections::btree_map::Entry::{Occupied, Vacant}; #[allow(unused_imports)] use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}; #[derive(Clone)] struct ConvexHullTrick { lines: Vec<(T, T)>, } impl ConvexHullTrick where T: std::ops::Add + std::ops::Mul + std::ops::Sub + Copy + PartialOrd, { fn new() -> Self { ConvexHullTrick { lines: Vec::new() } } fn check<'a>(mut l1: &'a (T, T), l2: &(T, T), mut l3: &'a (T, T)) -> bool { if l1 < l3 { std::mem::swap(&mut l1, &mut l3); } (l3.1 - l2.1) * (l2.0 - l1.0) >= (l2.1 - l1.1) * (l3.0 - l2.0) } fn add(&mut self, a: T, b: T) { while self.lines.len() >= 2 && Self::check( &self.lines[self.lines.len() - 2], self.lines.last().expect("cht Error!!"), &(a, b), ) { self.lines.pop(); } self.lines.push((a, b)); } fn calc(&self, i: usize, x: T) -> T { self.lines[i].0 * x + self.lines[i].1 } fn query(&self, x: T) -> T { if self.lines.len() == 1 { return self.calc(0, x); } let mut ng = 0; let mut ok = self.lines.len(); let check = |i| { if i + 1 == self.lines.len() { true } else { self.calc(i, x) < self.calc(i + 1, x) } }; if check(ng) { return self.calc(ng, x); } while ok-ng > 1 { let m = (ok + ng) / 2; if check(m) { ok = m; } else { ng = m; } } self.calc(ok, x) } } fn main() { use std::io::Write; let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); } macro_rules! printfln { () => (writeln!(out).unwrap()); ($($arg:tt)*) => (writeln!(out, $($arg)*).unwrap()); } let n = readl!(usize); let a = readlvec!(i64); let x = readlvec!(i64); let y = readlvec!(i64); let inf = 1_000_000_000_000_000; let mut dp = vec![inf; n+1]; dp[0] = 0; let mut cht = ConvexHullTrick::new(); for i in 0..dp.len()-1 { cht.add(x[i], dp[i] + x[i] * x[i] + y[i] * y[i]); dp[i+1] = min(dp[i+1], cht.query(-2 * a[i]) + a[i] * a[i]); } printfln!("{}", dp.last().unwrap()); }