#line 2 "cpp/convex.hpp" #include #include #include #include #include #include /** * @brief monotoneな行列において、各行の最小値を取る最小列番号を$O((H+W)\log H)$時間で得る * @param h 行数(行番号は[0..h-1]) * @param w 列数(列番号は[0..w-1]) * @param f 行列の要素を与える関数(行番号と列番号を引数にとって値を返す) * @param comp 要素の比較関数(最小値を知りたい場合はデフォルトのstd::less) * @return std::vector 各行の最小値列番号 */ template >> std::vector monotone_minima(int h, int w, const F& f, const Comp& comp = Comp()) { using T = std::invoke_result_t; assert(h >= 0); assert(w >= 0); std::vector res(h); std::stack> stk; // {i, j, l, r} : [i..j]行目の答えを求める。結果は[l..r]の範囲に収まることが保証されている。 stk.emplace(0, h-1, 0, w-1); while(!stk.empty()) { auto [i, j, l, r] = stk.top(); stk.pop(); int m = (i+j) / 2; T min_value = f(m, l); int min_idx = l; for(int k = l+1; k <= r; k++) { T value = f(m, k); if(comp(value, min_value)) { min_value = value; min_idx = k; } } res[m] = min_idx; if(i <= m-1) stk.emplace(i, m-1, l, min_idx); if(m+1 <= j) stk.emplace(m+1, j, min_idx, r); } return res; } template >> std::vector> online_offline_dp(int n, const F& f, const Comp& comp = Comp{}) { using T = std::invoke_result_t; std::vector> dp(n+1, std::nullopt); dp[0] = 0; // dp[l..r)の要素を、dp[l..r)からの遷移のみの範囲で求める auto solve_subproblem = [&](auto self, int l, int r) -> void { int mid = (l+r) / 2; if(mid-l >= 2) self(self, l, mid); auto submat = [&](int i, int j) { return dp[l+j].value() + f(l+j, mid+i); }; std::vector min_idx = monotone_minima(r-mid, mid-l, submat, comp); for(int i = 0; i < r-mid; i++) { T val = submat(i, min_idx[i]); if(!dp[mid+i] || comp(val, dp[mid+i].value())) { dp[mid+i] = val; } } if(r-mid >= 2) self(self, mid, r); }; solve_subproblem(solve_subproblem, 0, n+1); std::vector res(n+1); for(int i = 0; i <= n; i++) res[i] = dp[i].value(); return res; } #line 2 "test/yukicoder-705.test.cpp" #include int main() { using ll = long long; 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]; auto f = [&](int i, int j) { ll dx = std::abs(x[i] - a[j-1]); ll dy = std::abs(y[i]); return dx*dx*dx + dy*dy*dy; }; std::cout << online_offline_dp(n, f)[n] << std::endl; }