// AC // https://oj.uz/problem/view/CEOI17_building #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; mutable ll x; bool is_min; Line(ll m, ll k, ll x, bool is_min = false) : m {m}, k {k}, is_min {is_min} {} // pentru maxime - convex hull cu concavitatea in sus - panta trebuie sa cresca in hull // pentru minime - convex hull cu concavitatea in jos - panta trebuie sa sada in hull bool operator<(const Line& line) const { return is_min ? m > line.m : m < line.m; } bool operator<(ll x) const { return this->x < x; } }; template <bool is_min> struct CHT : multiset<Line, less<>> { static const ll INF = LLONG_MAX; ll div(ll a, ll b) { // "floor division" daca rezultatul impartirii este < 0 si exista rest, atunci scade 1 return a / b - ((a ^ b) < 0 && a % b); } // determina abscisa x de intersectie intre dreptele *a si *b // returneaza true daca linia *b trebuie stearsa bool isect(iterator a, iterator b) { // x este abscisa de intersectie intre dreapta curenta *a si urmatoarea *b if (b == end()) // nu exista linia b (deci a nu trebuie in pericol sa fie stearsa) { a->x = INF; return false; } if (a->m == b->m) { if (a->k < b->k) a->x = is_min ? INF : -INF; else a->x = is_min ? -INF : INF; } else a->x = div(b->k - a->k, a->m - b->m); // daca nu sunt paralele aflam abscisa de intersectie dintre *a si *b return a->x >= b->x; // daca *a si *b se intersecteaza la dreapta intersectiei *b cu *c(urmatoarea), atunci b trebuie eliminata } void add(ll m, ll k) { auto c = emplace(m, k, 0, is_min), b = c++, a = b; // acum a si b indica noua dreapta, c - urmatoarea din container // incercam sa eliminam linii din dreapta liniei noi (linia noua *b poate cauza stergeri in dreapta sa) while (isect(b, c)) // cat timp *c (urmatoarea dupa *b) trebuie eliminata c = erase(c); // se elimina (iteratorul b ramane pe loc, c merge spre dreapta) // linia noua *b de asemenea ar putea fi eliminata if (a != begin() && isect(--a, b)) isect(a, b = erase(b)); // b devine urmatorul nesters // linia noua ar putea sa duca la stergerea altor linii din stanga sa while ((b = a) != begin() && (--a)->x >= b->x) isect(a, erase(b)); // sterge b si calculeaza intersectia liniei a cu noul b } ll query(ll x) { auto l = *lower_bound(x); // operator<(int x) din Line return l.m * x + l.k; } }; void Solve() { CHT<true> 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; }