// 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=long long; #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>>; // generated by ChatGPT outside of contest time. // 各行の最小値を返す。行・列は 0-indexed。 // // 前提: // 任意の部分行列について、各行の「最左の最小値」の列番号が // 上の行から下の行へ非減少であること(全単調性)。 // f(r, c) の返す値は呼び出し間で変化しないこと。 // // 計算量: // f の評価回数 O(H + W) // 追加領域 O(H + W) // // ワンポイントアドバイス: // 下三角の場合、無効値の部分(ij)はINF-j // とするとうまくらしいよv template std::vector smawk( int H, int W, std::function f ) { if (H < 0 || W < 0) { throw std::invalid_argument("smawk: negative matrix size"); } if (H == 0) { return {}; } if (W == 0) { throw std::invalid_argument("smawk: no columns"); } std::vector rows(H); std::vector cols(W); std::iota(rows.begin(), rows.end(), 0); std::iota(cols.begin(), cols.end(), 0); // 最小値を取る最左の列番号を内部で求める。 std::vector argmin(H); auto solve = [&]( auto&& self, const std::vector& rs, const std::vector& cs ) -> void { if (rs.empty()) { return; } const std::size_t n = rs.size(); // 候補列を、行数以下になるまで削減する。 std::vector reduced; reduced.reserve(std::min(n, cs.size())); for (int c : cs) { while (!reduced.empty()) { const int r = rs[reduced.size() - 1]; // 同値なら左側の列を残す。 if (!(f(r, c) < f(r, reduced.back()))) { break; } reduced.pop_back(); } if (reduced.size() < n) { reduced.push_back(c); } } // 現在の行リストにおける奇数番目の行を再帰的に解く。 std::vector odd_rows; odd_rows.reserve(n / 2); for (std::size_t i = 1; i < n; i += 2) { odd_rows.push_back(rs[i]); } self(self, odd_rows, reduced); // 偶数番目の行を、隣接する奇数番目の行の解の間で探索する。 std::size_t left = 0; for (std::size_t i = 0; i < n; i += 2) { std::size_t right; if (i + 1 < n) { right = left; while (reduced[right] != argmin[rs[i + 1]]) { ++right; } } else { right = reduced.size() - 1; } const int r = rs[i]; int best_col = reduced[left]; T best_value = f(r, best_col); for (std::size_t j = left + 1; j <= right; ++j) { const int c = reduced[j]; T value = f(r, c); if (value < best_value) { best_value = std::move(value); best_col = c; } } argmin[r] = best_col; left = right; } }; solve(solve, rows, cols); std::vector result; result.reserve(H); for (int r = 0; r < H; ++r) { result.push_back(f(r, argmin[r])); } return result; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout<>n; vl a(n+1); for(int i=1;i<=n;i++)cin>>a[i]; vl s(n+2); for(int i=0;i<=n;i++)s[i+1]=s[i]+a[i]; vvl dp(n+2,vl(n+2)); auto cost=[&](int i,int j)->ll{ return (s[j]-s[i+1])*(s[j]-s[i+1]); }; for(int i=1;i<=n+1;i++)dp[1][i]=cost(0,i); const ll inf=1e18; for(int k=2;k<=n+1;k++){ auto f=[&](int i,int j)->ll{ if(i(n+2-k,n+2-k,f); for(int i=0;i=1;k--)cout<