#include #include #include #include using namespace std; const long long INF = 1000000000000000000LL; const int MAXN = 600000 + 5; class DynamicConvexHull { private: struct Point { /* Defines the progression of the form x * param + y */ long long x; long long y; bool is_query_point; mutable set::iterator par; set *master; // the set, containing this point Point () { } Point (long long x, long long y, bool is_query_point, set *master) : x(x), y(y), is_query_point(is_query_point), master(master) { } inline bool operator < (const Point &you) const { /* There are two possible situations: - We're adding a point to the convex hull; - We're looking for the optimal possible value of x * param + b for some param = x; In the first case, we will act just like we sort the points in Graham's algo. */ if (!is_query_point && !you.is_query_point) return (x > you.x); /* In the second case, we will use the fact that first, the progressions value will decrease, and after some point will start to increase again. */ if (is_query_point) { /* In this case, my object is a query with param = x. */ if (you.par == master->end()) return false; if (you.par->x < you.x) return ((you.y - you.par->y) <= x * (you.par->x - you.x)); else return ((you.y - you.par->y) >= x * (you.par->x - you.x)); } else { /* This is the previous case, vice-versa. */ if (par == master->end()) return true; if (par->x < x) return (y - par->y) > you.x * (par->x - x); else return (y - par->y) < you.x * (par->x - x); } } } ; typedef set::iterator position; set hull; /* The following routine removes the point, denoted by the iterator from the hull. */ inline void remove_point (position me) { /* We only need to ensure that the next point has a correct predecessor pointer. */ position next = me; ++next; if (next != hull.end()) next->par = me->par; hull.erase(me); } inline bool is_bad_turn (position center) { position next = center, prev = center; ++next; if (center == hull.begin() || next == hull.end()) return false; --prev; Point a = *prev, b = *center, c = *next; bool check_type = false; if (b.x < a.x) check_type ^= true; if (b.x < c.x) check_type ^= true; if (check_type) return (c.y - b.y) * (b.x - a.x) >= (a.y - b.y) * (b.x - c.x); else return (c.y - b.y) * (b.x - a.x) <= (a.y - b.y) * (b.x - c.x); } public: inline void add_progression (long long x, long long y) { Point me(x, y, false, &hull); position pos = hull.find(me); if (pos != hull.end() && pos->y >= y) return ; if (pos != hull.end()) remove_point(pos); hull.insert(me); /* Recalculate the pointer to the previous point for the next point.*/ pos = hull.find(me); position next = pos; ++next; if (next != hull.end()) next->par = pos; /* Calculate the pointer to the previous point for the current point.*/ if (pos != hull.begin()) { position prev = pos; --prev; pos->par = prev; } else pos->par = hull.end(); /* If the point is lying above the current hull, we can safely get rid of it. */ if (is_bad_turn(pos)) { remove_point(pos); return ; } /* Delete the points that became unnecessary and lay after the current one. */ while (next != hull.end() && is_bad_turn(next)) { remove_point(next); next = pos; ++next; } /* Delete the points that became unnecessary and lay before the current one. */ if (pos != hull.begin()) { position prev = pos; --prev; while (pos != hull.begin() && is_bad_turn(prev)) { remove_point(prev); prev = pos; --prev; } } } inline long long get_min_value_at (long long x) { if (hull.size() == 0) return INF; Point me(x, x, true, &hull); position opt = hull.lower_bound(me); --opt; return opt->x * x + opt->y; } }; class LineTree { private: struct Node { int l; int r; DynamicConvexHull dch; } tree[MAXN * 4]; public: void init (int pos, int l, int r) { tree[pos].l = l; tree[pos].r = r; if (l < r) { init(pos + pos, l, (l + r) / 2); init(pos + pos + 1, (l + r) / 2 + 1, r); } } void modify (int pos, int j, long long x, long long y) { tree[pos].dch.add_progression(x, y); if (tree[pos].l == tree[pos].r) return; if (tree[pos + pos].r >= j) modify(pos + pos, j, x, y); else modify(pos + pos + 1, j, x, y); } long long query (int pos, int l, int r, long long par) { if (tree[pos].l == l && tree[pos].r == r) return tree[pos].dch.get_min_value_at(par); else { long long ret = INF; if (l <= min(r, tree[pos + pos].r)) ret = min(ret, query(pos + pos, l, min(r, tree[pos + pos].r), par)); if (max(l, tree[pos + pos + 1].l) <= r) ret = min(ret, query(pos + pos + 1, max(l, tree[pos + pos + 1].l), r, par)); return ret; } } } lt; long long dp[MAXN]; int p[MAXN], a[MAXN], h[MAXN], n; pair srt[MAXN]; int main () { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &p[i]); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++) scanf("%d", &h[i]); for(int i = 1; i <= n; i++) srt[i] = make_pair(p[i], i); sort(srt + 1, srt + n + 1); lt.init(1, 1, n); lt.modify(1, 1, -2 * h[1], a[1] + h[1] * 1LL * h[1]); dp[1] = a[1]; for(int i = 2; i <= n; i++) { int idx = srt[i].second; dp[idx] = lt.query(1, 1, idx - 1, h[idx]) + h[idx] * 1LL * h[idx] + a[idx]; lt.modify(1, idx, -2 * h[idx], dp[idx] + h[idx] * 1LL * h[idx]); } printf("%lld\n", dp[n]); return 0; }