#include <set> #include <algorithm> #include <iostream> #include <climits> using namespace std; using ll = long long; const int MAXN = 1e5 + 5; const ll INF = 1e18 + 5; ll n, h[MAXN], w[MAXN]; ll dp[MAXN]; ll sp[MAXN]; void Read() { cin >> n; for (int i = 1; i <= n; ++i) cin >> h[i]; for (int i = 1; i <= n; ++i) { cin >> w[i]; sp[i] = sp[i - 1] + w[i]; } } struct Line { ll m, k; // m*x + k mutable ll x; bool operator < (const Line &other) const { return m > other.m; } // aici < pt maxim bool operator < (int x) const { return this->x < x; } ll operator()(ll x) const {return m * x + k;} }; 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 a, iterator b) { if (b == end()) {a->x = INF; return false;} if (a->m == b->m) a->x = (a->k < b->k ? INF : -INF); // aici invers pt maxim else a->x = div(b->k - a->k, a->m - b->m); return a->x >= b->x; } void add(ll m, ll k) { auto c = insert({m, k, 0}), b = c++, a = b; while (isect(b, c)) c = erase(c); if (a != begin() && isect(--a, b)) isect(a, b = erase(b)); while ((b = a) != begin() && (--a)->x >= b->x) isect(a, erase(b)); } ll query(ll x) { Line line = *lower_bound(x); return line(x); } }; void Solve() { CHT hull; fill(dp + 1, dp + n + 1, INF); dp[1] = 0; for (int i = 1; i <= n; ++i) { if (i > 1) dp[i] = hull.query(h[i]) + h[i] * h[i] + sp[i - 1]; hull.add(-2 * h[i], dp[i] + h[i] * h[i] - sp[i]); } cout << dp[n]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); Read(); Solve(); return 0; }