#include #define rep(i,a,b) for(int i=a;i=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() #pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (ba < l2.a; if (l2.type == maxQuery) return this->xLeft < l2.val; if (l2.type == minQuery) return this->xLeft > l2.val; } }; bool isMax; //whether or not saved envelope is top(search of max value) public: std::set< Line > hull; //envelope itself private: /* * INFO: Check position in hull by iterator * COMPLEXITY: O(1) */ bool hasPrev(std::set< Line >::iterator it) { return it != hull.begin(); } bool hasNext(std::set< Line >::iterator it) { return it != hull.end() && std::next(it) != hull.end(); } /* * INFO: Check whether line l2 is irrelevant * NOTE: Following positioning in hull must be true * l1 is next left to l2 * l2 is right between l1 and l3 * l3 is next right to l2 * COMPLEXITY: O(1) */ bool irrelevant(const Line &l1, const Line &l2, const Line &l3) { return intersectX(l1, l3) <= intersectX(l1, l2); } bool irrelevant(std::set< Line >::iterator it) { return hasPrev(it) && hasNext(it) && (isMax && irrelevant(*std::prev(it), *it, *std::next(it)) || !isMax && irrelevant(*std::next(it), *it, *std::prev(it))); } /* * INFO: Updates 'xValue' of line pointed by iterator 'it' * COMPLEXITY: O(1) */ std::set< Line >::iterator updateLeftBorder(std::set< Line >::iterator it) { if (isMax && !hasPrev(it) || !isMax && !hasNext(it)) return it; double val = intersectX(*it, isMax ? *std::prev(it) : *std::next(it)); Line buf(*it); it = hull.erase(it); buf.xLeft = val; it = hull.insert(it, buf); return it; } public: explicit ConvexHullDynamic(bool isMax = false) : isMax(isMax) {} /* * INFO: Adding line to the envelope * Line is of type 'y=a*x+b' represented by 2 coefficients 'a' and 'b' * COMPLEXITY: Adding N lines(N calls of function) takes O(N*log N) time */ void addLine(coef_t a, coef_t b) { //find the place where line will be inserted in set Line l3 = Line(a, b); auto it = hull.lower_bound(l3); //if parallel line is already in set, one of them becomes irrelevant if (it != hull.end() && areParallel(*it, l3)) { if (isMax && it->b < b || !isMax && it->b > b) it = hull.erase(it); else return; } //try to insert it = hull.insert(it, l3); if (irrelevant(it)) { hull.erase(it); return; } //remove lines which became irrelevant after inserting line while (hasPrev(it) && irrelevant(std::prev(it))) hull.erase(std::prev(it)); while (hasNext(it) && irrelevant(std::next(it))) hull.erase(std::next(it)); //refresh 'xLine' it = updateLeftBorder(it); if (hasPrev(it)) updateLeftBorder(std::prev(it)); if (hasNext(it)) updateLeftBorder(std::next(it)); } val_t getBest(coord_t x) const { Line q; q.val = x; q.type = isMax ? Line::Type::maxQuery : Line::Type::minQuery; auto bestLine = hull.lower_bound(q); if (isMax) --bestLine; return bestLine->valueAt(x); } }; /*---------------------------------------------------------------------------------------------------             ∧_∧       ∧_∧  (´<_` )  Welcome to My Coding Space!      ( ´_ゝ`) /  ⌒i     /   \    | |     /   / ̄ ̄ ̄ ̄/  |   __(__ニつ/  _/ .| .|____      \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ int N; ll A[301010], X[301010], Y[301010]; ll dp[301010]; ConvexHullDynamic ch; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 1, N + 1) cin >> A[i]; rep(i, 1, N + 1) cin >> X[i]; rep(i, 1, N + 1) cin >> Y[i]; rep(i, 0, N + 1) dp[i] = infl; dp[0] = 0; /* O(N^2) rep(i, 1, N + 1) { rep(j, 0, i) { ll dx = abs(A[i] - X[j + 1]); ll dy = Y[j + 1]; ll z = dp[j] + dx + dy; chmin(dp[i], z); } }*/ rep(i, 1, N + 1) { rep(j, 0, i) if (A[i] < X[j + 1]) chmin(dp[i], dp[j] + X[j + 1] - A[i] + Y[j + 1]); rep(j, 0, i) if (A[i] >= X[j + 1]) chmin(dp[i], dp[j] + A[i] - X[j + 1] + Y[j + 1]); } cout << dp[N] << endl; }