// includes {{{ #include #include #include #include #include #include #include #include #include #include #include #include // #include // #include // #include // #include // #include // }}} using namespace std; using ll = long long; // #undef DEBUG // #define DEBUG // DEBUG {{{ #include #include #include #include #include #include #include #include #include // clang-format off template typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple const &){} template typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple const & t){ os << (n==0?"":", ") << get(t); _ot(os, t); } template ostream & operator<<(ostream &o, tuple const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; } template ostream & operator<<(ostream &o, pair const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; } template < class T > ostream &operator<<(ostream &o, const stack &a) { o << "{"; for(auto tmp = a; tmp.size(); tmp.pop()) o << (a.size() == tmp.size() ? "" : ", ") << tmp.top(); o << "}"; return o; } template ostream &operator<<(ostream &os, priority_queue a) { os << "{ (top) "; while(a.size()) os << a.top() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; } template ostream &operator<<(ostream &os, queue a) { os << "{ "; while(a.size()) os << a.front() << (a.size() == 1 ? "" : ", "), a.pop(); os << " }"; return os; } #ifdef DEBUG #if !defined(DEBUG_OUT) #define DEBUG_OUT cerr #endif #if !defined(DEBUG_LEFT) #define DEBUG_LEFT "\e[1;36m" #endif #if !defined(DEBUG_RIGHT) #define DEBUG_RIGHT ":\e[m" #endif #define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);DEBUG_OUT< inline void dump1D(T &d, size_t sizey) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << d[i] << (i + 1 == sizey ? "" : " "); } DEBUG_OUT << endl; } template < class T, class = typename iterator_traits< decltype(begin(T())) >::value_type, class = typename enable_if::value>::type > ostream &operator<<(ostream &o, const T &a) { o << "{"; for(auto ite = begin(a); ite != end(a); ++ite) o << (ite == begin(a) ? "" : ", ") << *ite; o << "}"; return o; } #else #define dump(...) (42) #define dump2D(...) (42) #define dump1D(...) (42) template < class T, class = typename iterator_traits< decltype(begin(T())) >::value_type, class = typename enable_if::value>::type > ostream &operator<<(ostream &o, const T &a) { for(auto ite = begin(a); ite != end(a); ++ite) o << (ite == begin(a) ? "" : " ") << *ite; return o; } #endif // clang-format on // }}} constexpr int N = 3e5; int n; ll a[N]; ll x[N]; ll y[N]; // D(0) is given // D(i) = f( min(0 <= j < i, D(j) + w(j, i)) , i) // w must satisfy Convex QI // by default, f is identity function // Convex QI Speedup {{{ #include #include #include #include #include template < class T, class W, class F = function< T(const T &) > > auto ConvexQISpeedup(T d0, size_t n, const W &w, const F &f = [](const T &t) { return t; }) { #ifdef DEBUG static_assert(is_same< T, decltype(w(0, 0)) >::value, "T must equal to typeof w(...)"); static_assert(is_same< T, decltype(f(T())) >::value, "T must equal to typeof f(...)"); #endif vector< T > D(n + 1); D[0] = d0; // C(j, i) = D(j) + w(j, i) auto C = [&](size_t j, size_t i) { return D[j] + w(j, i); }; // search the first time to choose l rather than k // if w satisfies Closest Zero Property, you can speedup h auto h = [&](size_t l, size_t k) { assert(l < k && k < n + 1); size_t ok = n + 1, ng = k; while(ok - ng > 1) { size_t mid = (ok + ng) >> 1; if(C(l, mid) <= C(k, mid)) ok = mid; else ng = mid; } return ok; }; // (k, h) where k is index and h is the time to die stack< pair< size_t, size_t > > S; S.emplace(0, n + 1); for(size_t i = 1; i <= n; i++) { size_t j = S.top().first; if(C(i - 1, i) >= C(j, i)) D[i] = f(C(j, i)); else { D[i] = f(C(i - 1, i)); while(S.size() && C(i - 1, S.top().second - 1) < C(S.top().first, S.top().second - 1)) S.pop(); if(S.empty()) S.emplace(i - 1, n + 1); else S.emplace(j, h(S.top().first, i - 1)); } if(S.top().second == i + 1) S.pop(); } return D; } // }}} // D(0) is given // D(i) = f( min(0 <= j < i, D(j) + w(j, i)) , i) // w must satisfy Concave QI = Monge // by default, f is identity function // Concave QI ( = Monge ) Speedup {{{ #include #include #include #include #include template < class T, class W, class F = function< T(const T &) > > auto ConcaveQISpeedup(T d0, size_t n, const W &w, const F &f = [](const T &t) { return t; }) { #ifdef DEBUG static_assert(is_same< T, decltype(w(0, 0)) >::value, "T must equal to typeof w(...)"); static_assert(is_same< T, decltype(f(T())) >::value, "T must equal to typeof f(...)"); #endif vector< T > D(n + 1); D[0] = d0; // C(j, i) = D(j) + w(j, i) auto C = [&](size_t j, size_t i) { return D[j] + w(j, i); }; // search the first time to choose l rather than k // if w satisfies Closest Zero Property, you can speedup h auto h = [&](size_t l, size_t k) { assert(k < l && l < n + 1); size_t ok = n + 1, ng = l; while(ok - ng > 1) { size_t mid = (ok + ng) >> 1; if(C(l, mid) <= C(k, mid)) ok = mid; else ng = mid; } return ok; }; // (k, h) where k is index and h is the time to kill predecessor deque< pair< size_t, size_t > > Q; Q.emplace_back(0, 1); for(size_t i = 1; i <= n; i++) { assert(Q.size()); size_t j = Q.front().first; if(C(i - 1, i) <= C(j, i)) { D[i] = f(C(i - 1, i)); Q.clear(); Q.emplace_back(i - 1, i + 1); } else { D[i] = f(C(j, i)); while(Q.size() > 1 && C(i - 1, Q.back().second) <= C(Q.back().first, Q.back().second)) Q.pop_back(); size_t k = h(i - 1, Q.back().first); if(k < n + 1) Q.emplace_back(i - 1, k); if(i + 1 == Q[1].second) Q.pop_front(); else Q.front().second++; } } return D; } // }}} #if 0 #convex QIについて l < kについて "kではなくl ( = 小さい方) を選ぶ利点" はだんだん大きくなる C(j, i) は i から j を選ぶときの損 のように考えればよい (損を最小化する) #endif constexpr ll inf = 1e18; inline ll pow3(ll x) { return x * x * x; } // 1-indexed ll g(int k, int i) { assert(k < i); return pow3(abs(x[k] - a[i - 1])) + pow3(y[k]); } int main() { ios::sync_with_stdio(false), cin.tie(0); cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 0; i < n; i++) cin >> x[i]; for(int i = 0; i < n; i++) cin >> y[i]; cout << ConcaveQISpeedup< ll >(0, n, g)[n] << endl; return 0; }