#include #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wsign-conversion" //!===========================================================!// //! dP dP dP !// //! 88 88 88 !// //! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !// //! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !// //! 88 88 88. ... 88. .88 88. .88 88. ... 88 !// //! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !// //!===========================================================!// using ld = long double; using ll = long long; using ull = unsigned long long; std::mt19937 mt{std::random_device{}()}; template constexpr T INF = std::numeric_limits::max() / 4; template constexpr T MOD = static_cast(1000000007); template constexpr F PI() { return 3.1415926535897932385; } template std::ostream& operator<<(std::ostream& os, const std::array& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::deque& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::multimap& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::multiset& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::map& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::pair& v) { return (os << "<" << v.first << "," << v.second << ">"); } template std::ostream& operator<<(std::ostream& os, const std::priority_queue& v) { auto q = v; os << "["; while (not q.empty()) { os << q.top() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::queue& v) { auto q = v; os << "["; while (not q.empty()) { os << q.front() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::set& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::stack& v) { auto q = v; os << "["; while (not q.empty()) { os << q.top() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::unordered_multimap& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_multiset& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_map& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_set& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::vector& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } #define SHOW(...) (std::cerr << "(" << #__VA_ARGS__ << ") = ("), HogeHogeSansuu(__VA_ARGS__), std::cerr << ")" << std::endl; void HogeHogeSansuu() { ; } template void HogeHogeSansuu(const T x) { std::cerr << x; } template void HogeHogeSansuu(const T x, Args... args) { (std::cerr << x << ", "), HogeHogeSansuu(args...); } template std::vector Vec(const std::size_t n, T v) { return std::vector(n, v); } template auto Vec(const std::size_t n, Args... args) { return std::vector(n, Vec(args...)); } template constexpr T PopCount(T v) { return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast(v * 0x0101010101010101ULL >> 56 & 0x7f); } template constexpr T log2p1(T v) { return v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), PopCount(v); } template constexpr bool ispow2(const T v) { return (v << 1) == (T(1) << (log2p1(v))); } template constexpr T ceil2(const T v) { return ispow2(v) ? v : T(1) << log2p1(v); } template constexpr T floor2(const T v) { return v == 0 ? T(0) : ispow2(v) ? v : T(1) << (log2p1(v) - 1); } //!=================================================================================!// //! .d88888b oo dP a88888b. dP dP d888888P !// //! 88. "' 88 d8' '88 88 88 88 !// //! 'Y88888b. dP 88d8b.d8b. 88d888b. 88 .d8888b. 88 88aaaaa88a 88 !// //! '8b 88 88''88''88 88' '88 88 88ooood8 88 88 88 88 !// //! d8' .8P 88 88 88 88 88. .88 88 88. ... Y8. .88 88 88 88 !// //! Y88888P dP dP dP dP 88Y888P' dP '88888P' Y88888P' dP dP dP !// //! 88 !// //! dP !// //!=================================================================================!// template struct SimpleCHT { using L = std::pair; std::vector lines; public: void add(const T a, const T b) { auto check = [](auto&& self, const L& l1, const L& l2, const L& l3) -> bool { return l1 < l3 ? self(self, l3, l2, l1) : V(l3.second - l2.second) * (l2.first - l1.first) >= V(l2.second - l1.second) * (l3.first - l2.first); }; while (lines.size() >= 2 and check(check, *(lines.end() - 2), lines.back(), {a, b})) { lines.pop_back(); } lines.push_back({a, b}); } V query(const T x) const { static std::size_t head = 0; auto f = [&](const std::size_t i, const T x) -> V { return (V)lines[i].first * x + lines[i].second; }; for (; lines.size() - head >= 2 and f(head, x) > f(head + 1, x); head++) {} return f(head, x); } }; int main() { int N; std::cin >> N; std::vector a(N), x(N), y(N); for (int i = 0; i < N; i++) { std::cin >> a[i]; } for (int i = 0; i < N; i++) { std::cin >> x[i]; } for (int i = 0; i < N; i++) { std::cin >> y[i]; } SimpleCHT cht; cht.add(-2 * x[0], x[0] * x[0] + y[0] * y[0]); for (int i = 1; i < N; i++) { const ll dp = cht.query(a[i - 1]) + a[i - 1] * a[i - 1]; cht.add(-2 * x[i], x[i] * x[i] + y[i] * y[i] + dp); } std::cout << cht.query(a[N - 1]) + a[N - 1] * a[N - 1] << std::endl; return 0; }