#include #include #include #define llint long long #define inf 1e18 using namespace std; typedef pair P; struct LiChaoTree{ int size; vector

seg; LiChaoTree(){} LiChaoTree(int size){ this->size = size; seg.resize(1<<(size+1)); } void init() { for(int i = 0; i < (1<<(size+1)); i++) seg[i] = make_pair(0, inf); } llint calc(P f, llint x) { return f.first * x + f.second; } llint query(int x) { int i = x + (1 << size); llint ret = inf; while(i >= 1){ ret = min(ret, calc(seg[i], x)); i /= 2; } return ret; } void add(int k, int l, int r, P f) { int m = (l+r)/2; if(calc(f, m) < calc(seg[k], m)) swap(seg[k], f); bool L = (calc(f, l) < calc(seg[k], l)), R = (calc(f, r) < calc(seg[k], r)); if(L == R) return; if(L) add(k*2, l, m, f); if(R) add(k*2, m+1, r, f); } void addSegment(int a, int b, int k, int l, int r, P f) { if(b < l || r < a) return; if(a <= l && r <= b){ add(k, l, r, f); return; } addSegment(a, b, k*2, l, (l+r)/2, f); addSegment(a, b, k*2+1, (l+r)/2+1, r, f); } void addSegment(int a, int b, llint p, llint q) { addSegment(a, b, 1, 0, (1<> n; for(int i = n; i >= 1; i--) cin >> a[i]; for(int i = n; i >= 1; i--) cin >> x[i]; for(int i = n; i >= 1; i--) cin >> y[i]; lct.init(); dp[0] = 0; lct.addLine(-2*a[1], a[1]*a[1]+dp[0]); for(int i = 1; i <= n; i++){ dp[i] = lct.query(x[i]) + x[i]*x[i] + y[i]*y[i]; lct.addLine(-2*a[i+1], a[i+1]*a[i+1]+dp[i]); } cout << dp[n] << endl; return 0; }