// 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>>; //https://qandori.github.io/cp-library/data_structure/li_chao_tree.hpp.html #line 1 "data_structure/li_chao_tree.hpp" #include #include #include #include #include #include #include #include #include #include template , std::conditional_t<(sizeof(T) < 8), std::int64_t, __int128_t>, T>> class LiChaoTree { static_assert((std::is_integral_v && std::is_signed_v && sizeof(T) <= 8) || std::is_floating_point_v); struct Line { T a, b; template V eval(T x) const { return V(R(a) * R(x) + R(b)); } }; int n = 0, base = 1; bool wide = false, dense = false; std::vector xs; std::vector lines; std::vector state; template static bool better(V a, V b) { if constexpr (maximize) return a > b; else return a < b; } template void insert(int k, int l, int width, Line f) { for (;;) { Line &g = lines[k]; if (!(state[k] & 1)) { g = f; state[k] = 3; return; } if (f.a == g.a) { if (better(f.b, g.b)) g = f; return; } int half = width >> 1, m = l + half; if (better(f.template eval(xs[m]), g.template eval(xs[m]))) std::swap(f, g); if (!half) return; bool right = better(f.a, g.a); int edge = right ? l + width - 1 : l; if (!better(f.template eval(xs[edge]), g.template eval(xs[edge]))) return; k = k * 2 + right; if (right) l = m; width = half; } } template void insert_segment(int k, int l, int r, int ql, int qr, Line f) { if (ql <= l && r <= qr) { insert(k, l, r - l, f); return; } if (state[k] & 1) { const Line &g = lines[k]; if (f.a == g.a) { if (!better(f.b, g.b)) return; } else { int edge = better(f.a, g.a) ? std::min(r, qr) - 1 : std::max(l, ql); if (!better(f.template eval(xs[edge]), g.template eval(xs[edge]))) return; } } state[k] |= 2; int m = (l + r) >> 1; if (ql < m) insert_segment(k * 2, l, m, ql, qr, f); if (m < qr) insert_segment(k * 2 + 1, m, r, ql, qr, f); } void check(Line f, int l, int r) { if constexpr (std::is_integral_v && std::is_same_v) { if (!wide) { R a = f.template eval(xs[l]), b = f.template eval(xs[r - 1]); wide = a != R(std::int64_t(a)) || b != R(std::int64_t(b)); } } } template decltype(auto) dispatch(F f) const { if constexpr (std::is_integral_v && std::is_same_v) { if (!wide) return f.template operator()(); } return f.template operator()(); } int lower(T x) const { if (n <= 1) return n && xs[0] < x; if constexpr (std::is_integral_v) if (dense) return int(std::clamp<__int128_t>(__int128_t(x) - xs[0], 0, n)); int i = 0; for (int step = base >> 1; step; step >>= 1) i += int(xs[i + step - 1] < x) * step; return std::min(n, i + int(xs[i] < x)); } template std::optional query_impl(int i) const { assert(0 <= i && i < n); V result = maximize ? std::numeric_limits::lowest() : std::numeric_limits::max(); bool found = false; for (int k = 1, bit = base >> 1;; bit >>= 1) { if (!state[k]) break; if (state[k] & 1) { V value = lines[k].template eval(xs[i]); if ((std::is_floating_point_v && !found) || better(value, result)) result = value; found = true; } if (!bit) break; k = k * 2 + bool(i & bit); } if (found) return result; return std::nullopt; } public: using value_type = R; explicit LiChaoTree(std::vector coordinates = {}) { build(std::move(coordinates)); } void build(std::vector coordinates) { if (!std::is_sorted(coordinates.begin(), coordinates.end())) std::sort(coordinates.begin(), coordinates.end()); coordinates.erase(std::unique(coordinates.begin(), coordinates.end()), coordinates.end()); assert(coordinates.size() <= std::size_t(1) << 29); n = static_cast(coordinates.size()); if constexpr (std::is_integral_v) dense = n && __int128_t(coordinates.back()) - coordinates[0] == n - 1; base = int(std::bit_ceil(unsigned(std::max(1, n)))); xs = std::move(coordinates); if (n) xs.resize(base, xs.back()); lines.resize(base * 2); state.assign(base * 2, 0); wide = false; } int size() const { return n; } void clear() { std::fill(state.begin(), state.end(), 0); wide = false; } T coordinate(int i) const { assert(0 <= i && i < n); return xs[i]; } int index(T x) const { int i = lower(x); assert(i < n && xs[i] == x); return i; } void add_line(T a, T b) { if (n) { Line f{a, b}; check(f, 0, n); dispatch([&]() { insert(1, 0, base, f); }); } } void add_segment_index(int l, int r, T a, T b) { assert(0 <= l && l <= r && r <= n); if (l < r) { Line f{a, b}; check(f, l, r); dispatch([&]() { insert_segment(1, 0, base, l, r == n ? base : r, f); }); } } void add_segment(T l, T r, T a, T b) { assert(l <= r); int left = lower(l); int right = lower(r); add_segment_index(left, right, a, b); } std::optional query_index(int i) const { return dispatch([&]() { return query_impl(i); }); } std::optional query(T x) const { return query_index(index(x)); } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout<>n; vl a(n); cin>>a; vl s(n+1); for(int i=0;i> cht(n+1); for(int i=0;i<=n;i++){ vl v; for(int j=i;j<=n;j++)v.push_back(s[j]); cht[i].build(v); } vvl dp(n+2,vl(n+2)); cht[0].add_line(0,0); vl ans(n+1,1e18); for(int i=1;i<=n+1;i++){ for(int j=i-1;j>=0;j--){ dp[i][j+1]=cht[j].query(s[i-1]).value()+s[i-1]*s[i-1]; if(i<=n)cht[j+1].add_line(-2*s[i],dp[i][j+1]+s[i]*s[i]); ans[i-j-1]=min(ans[i-j-1],dp[i][j+1]); } if(i<=n)ans[i]=min(ans[i],s[i]*s[i]); //cout<