// SPDX-License-Identifier: CC0-1.0 // // [English] // To the extent possible under law, the author(s) have dedicated all copyright // and related and neighboring rights to this software to the public domain // worldwide. This software is distributed without any warranty. // See for details. // // [日本語] // 法律上可能な範囲で、著作者はこのソフトウェアに関する著作権および // 著作隣接権を含むすべての関連する権利を、全世界でパブリックドメインに // 提供しています。本ソフトウェアは一切の保証なく配布されます。 // 自由にコピー・改変・再配布・商用利用できます(クレジット表記は不要です)。 // 詳細は を参照してください。 // ※ 英語の文面および CC0 1.0 の正式な条文(英語)が優先されます。 #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll=std::int64_t; #include using mint=atcoder::modint998244353; ostream& operator<<(ostream& os,const mint& x){ os<>(istream& is,mint& x){ int t; is>>t; x=t; return is; } template ostream& operator<<(ostream& os,const pair& p); template istream& operator>>(istream& is,pair& p); template ostream& operator<<(ostream& os,const array& arr); template istream& operator>>(istream& is,array& arr); template ostream& operator<<(ostream& os,const vector& vec); template istream& operator>>(istream& is,vector& vec); template ostream& operator<<(ostream& os,const pair& p){ os< istream& operator>>(istream& is,pair& p){ is>>p.first>>p.second; return is; } template ostream& operator<<(ostream& os,const array& arr){ for(int i=0;i istream& operator>>(istream& is,array& arr){ for(int i=0;i>arr[i]; return is; } template ostream& operator<<(ostream& os,const vector& vec){ for(int i=0;i<(int)vec.size();i++)os< istream& operator>>(istream& is,vector& vec){ for(int i=0;i<(int)vec.size();i++)is>>vec[i]; return is; } template void input_vec(Vecs&... vs) { const auto n = get<0>(tie(vs...)).size(); for (size_t i = 0; i < n; ++i) ((cin >> vs[i]), ...); } template void output_vec(const Vecs&... vs) { const auto n = get<0>(tie(vs...)).size(); for (size_t i = 0; i < n; ++i) { bool first = true; (((cout << (exchange(first, false) ? "" : " ") << vs[i])), ...); cout << endl; } } template vector make_unique(vector vec){ ranges::sort(vec); vec.erase(unique(vec.begin(),vec.end()),vec.end()); return vec; } vector Iota(int n,int s=0){ vector res(n); iota(res.begin(),res.end(),s); return res; } vector Iotall(int n,ll s=0){ vector res(n); iota(res.begin(),res.end(),s); return res; } void YESNO(bool f){ if(f)cout<<"Yes"<; using vvl=vector>; using vvvl=vector>>; using vi=vector; using vvi=vector>; using vvvi=vector>>; namespace larsch_detail { template class RowMinima { using Evaluate = std::function; int n_; Evaluate evaluate_; int next_row_ = 0; int bound_ = 0; std::vector columns_; std::unique_ptr> child_; public: // evaluate(row, col) の有効領域は 0 <= col <= row < n。 // 将来の行を評価してもよいが、列はオンラインに利用する。 RowMinima(int n, Evaluate evaluate) : n_(n), evaluate_(std::move(evaluate)) { const int m = n_ / 2; if (m > 0) { columns_.reserve(static_cast(m)); child_ = std::make_unique>( m, [this](int row, int col) -> T { return evaluate_(2 * row + 1, columns_[col]); } ); } } // 子の評価関数が this を参照するため、移動も禁止する。 RowMinima(const RowMinima&) = delete; RowMinima& operator=(const RowMinima&) = delete; RowMinima(RowMinima&&) = delete; RowMinima& operator=(RowMinima&&) = delete; // 行 0, 1, ..., n - 1 の順に、最小値を取る列を返す。 int next_argmin() { const int row = next_row_++; if ((row & 1) != 0) { // 直前の先読みで扱っていない新しい列だけを比較する。 if (evaluate_(row, row) < evaluate_(row, bound_)) { return row; } return bound_; } const int begin = bound_; int end = n_ - 1; if (row + 1 < n_) { const int reduced_row = row / 2; const int capacity = n_ / 2; if (reduced_row == 0) { columns_.push_back(0); } else { // 列削減。先頭 reduced_row 列は再帰側で使用済みなので // 変更せず、それ以降の候補だけを削除する。 for (int col = row - 1; col <= row; ++col) { while ( static_cast(columns_.size()) > reduced_row ) { const int rank = static_cast(columns_.size()) - 1; if ( evaluate_(2 * rank + 1, col) < evaluate_(2 * rank + 1, columns_.back()) ) { columns_.pop_back(); } else { break; } } if ( static_cast(columns_.size()) < capacity ) { columns_.push_back(col); } } } // 次の奇数行を、現時点で利用可能な列だけで先読みする。 end = columns_[child_->next_argmin()]; } bound_ = end; // 単調性により、この区間だけ調べればよい。 int best = begin; for (int col = begin + 1; col <= end; ++col) { if (evaluate_(row, col) < evaluate_(row, best)) { best = col; } } return best; } }; } // namespace larsch_detail // A(i, k, dp_k) = dp[k] + w(k, i) // // 前提: // - A は最小化の向きの Monge 性を満たす。 // - 同じ引数に対する A の返値は変化しない。 // - 評価と比較でオーバーフローや NaN が発生しない。 // // 戻り値: // dp[0] = 0 // dp[i] = min_{0 <= k < i} A(i, k, dp[k]) (1 <= i <= N) // // 計算量: // A の評価回数 O(N)、追加領域 O(N)。 template std::vector larsch(int N, Matrix A) { if (N < 0) { throw std::invalid_argument("larsch: N must be nonnegative"); } std::vector dp( static_cast(N) + 1, T{0} ); if (N == 0) { return dp; } // 内部の行 row を、画像の行 i = row + 1 に対応させる。 auto evaluate = [&](int row, int col) -> T { return std::invoke( A, row + 1, col, std::as_const(dp[col]) ); }; larsch_detail::RowMinima solver(N, evaluate); for (int row = 0; row < N; ++row) { const int col = solver.next_argmin(); dp[row + 1] = evaluate(row, col); } return dp; } // Aは(i,j,dp_j)を受け取って値を返します // 普通のk辺最短路ならA(i,j,dp_j)=dp_j+w(j,i)とすればok int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout<>n; vl a(n),x(n),y(n); cin>>a>>x>>y; auto w=[&](int i,int j){ j--; return abs((a[j]-x[i])*(a[j]-x[i])*(a[j]-x[i]))+abs(y[i]*y[i]*y[i]); }; auto ans=larsch(n,[&](int i,int j,ll dp_j)->ll{ return dp_j+w(j,i); }); cout<