#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define mind(a,b) (a>b?b:a) #define maxd(a,b) (a>b?a:b) #define absd(x) (x<0?-(x):x) #define pow2(x) ((x)*(x)) #define rep(i,n) for(int i=0; i=0; --i) #define repl(i,s,n) for(int i=s; i<=n; ++i) #define replr(i,s,n) for(int i=n; i>=s; --i) #define repf(i,s,n,j) for(int i=s; i<=n; i+=j) #define repe(e,obj) for(auto e : obj) #define SP << " " << #define COL << " : " << #define COM << ", " << #define ARR << " -> " << #define PNT(STR) cout << STR << endl #define POS(X,Y) "(" << X << ", " << Y << ")" #define DEB(A) " (" << #A << ") " << A #define DEBREP(i,n,val) for(int i=0; i P; typedef pair PI; typedef pair IP; typedef pair PP; typedef priority_queue, greater

> pvqueue; #define N 200004 typedef pair line; class LiChaoTree { int n; ll xs[N]; line data[N]; bool u[N]; ll f(line &l, ll x) { return l.first*x + l.second; } void _add_line(line ln) { int k = 0, l = 0, r = n; while(1) { int m = (l + r) / 2; if(!u[k]) { data[k] = ln; u[k] = true; return; } ll lx = xs[l], mx = xs[m], rx = xs[r-1]; bool left = (f(ln, lx) < f(data[k], lx)); bool mid = (f(ln, mx) < f(data[k], mx)); bool right = (f(ln, rx) < f(data[k], rx)); if(left && right) { data[k] = ln; return; } if(!left && !right) { return; } if(mid) { swap(data[k], ln); } if(left != mid) { k = 2*k+1; r = m; } else { k = 2*k+2; l = m; } } } ll _query(int k, ll x) { k += n - 1; ll s = u[k] ? f(data[k], x) : INFLL; while(k) { k = (k - 1) / 2; if(u[k]) { ll r = f(data[k], x); s = mind(s, r); } } return s; } public: LiChaoTree(vector &ps) { int n0 = ps.size(); n = 1; while(n < n0) n <<= 1; rep(i, n) u[i] = false; rep(i, n0) xs[i] = ps[i]; repl(i, n0, n-1) xs[i] = INF; } void add_line(ll p, ll q) { _add_line(line(p, q)); } ll query(int i) { return _query(i, xs[i]); } }; int n; ll x[N], y[N]; int main() { cin >> n; vector a; rep(i, n) { ll v; cin >> v; a.push_back(v); } rep(i, n) cin >> x[i]; rep(i, n) cin >> y[i]; LiChaoTree lct(a); ll v = 0; rep(i, n) { lct.add_line(-2*x[i], x[i]*x[i] + y[i]*y[i] + v); v = lct.query(i) + a[i]*a[i]; } cout << v << endl; return 0; }