#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(a) a.begin(),a.end() typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef unsigned long long ull; typedef vector<int> vi; struct Line{ mutable ll m,c,p; bool operator<(const Line &o) const {return m < o.m;} bool operator<(ll x) const {return p < x;} }; struct CHT : multiset<Line,less<>> { static const ll inf = LLONG_MAX; ll div(ll a, ll b){ return a/b - ((a^b)<0 && (a%b)); } bool isect(iterator x, iterator y){ if(y==end()) return x->p=inf,0; if(x->m==y->m) x->p = x->c > y->c ? inf : -inf; else x->p = div(x->c - y->c, y->m - x->m); return x->p >= y->p; } void add(ll m, ll c){ auto z = insert({-m,-c,0}), y = z++, x = y; while(isect(y,z)) z = erase(z); if(x!=begin() && isect(--x,y)) isect(x,y=erase(y)); while((y=x)!=begin() && (--x)->p >= y->p) isect(x,erase(y)); } ll get(ll x){ auto l = *lower_bound(x); return - l.m * x - l.c; } }; const int mxn = 1e5+1; ll h[mxn],pref[mxn]; void solve(){ int n; cin >> n; for(int i = 1; i <= n; i++) cin >> h[i]; for(int i = 1; i <= n; i++){ cin >> pref[i]; pref[i] += pref[i-1]; } CHT cht; cht.add(-2*h[1],h[1]*h[1]-pref[1]); for(int i = 2; i <= n; i++){ ll dp = pref[i-1] + h[i]*h[i] + cht.get(h[i]); if(i==n) cout << dp; cht.add(-2*h[i],h[i]*h[i] - pref[i] + dp); } } signed main(){ cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while(t--){solve();} }