#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 300004 class LiChaoTree { int n; ll xs[4*N]; ll p[4*N], q[4*N]; bool u[4*N]; void _add_line(ll a, ll b) { int k = 0, l = 0, r = n; while(r-l > 0) { int m = (l + r) / 2; if(!u[k]) { p[k] = a; q[k] = b; u[k] = true; return; } ll lx = xs[l], mx = xs[m], rx = xs[r-1]; ll pk = p[k], qk = q[k]; bool left = (a*lx+b < pk*lx+qk); bool mid = (a*mx+b < pk*mx+qk); bool right = (a*rx+b < pk*rx+qk); if(left && right) { p[k] = a; q[k] = b; return; } if(!left && !right) { return; } if(mid) { swap(p[k], a); swap(q[k], b); } 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] ? p[k]*x+q[k] : INFLL; while(k > 0) { k = (k - 1) / 2; if(u[k]) { ll r = p[k]*x+q[k]; s = mind(s, r); } } return s; } public: LiChaoTree(int n0, ll ps[N]) { n = 1; while(n < 2*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 a, ll b) { _add_line(a, b); } ll query(int i) { return _query(i, xs[i]); } }; int n; ll a[N], x[N], y[N]; int main() { cin >> n; rep(i, n) cin >> a[i]; rep(i, n) cin >> x[i]; rep(i, n) cin >> y[i]; LiChaoTree lct(n, 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; }