This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/952
// competitive-verifier: TLE 2
// competitive-verifier: MLE 512
#include <iostream>
#include <numeric>
#include "src/Optimization/LiChaoTree.hpp"
using namespace std;
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N;
cin >> N;
int A[N];
for (int i= 0; i < N; ++i) cin >> A[i];
long long S[N + 1], dp[N + 2], ans[N];
S[0]= 0;
for (int i= 0; i < N; ++i) S[i + 1]= S[i] + A[i];
static constexpr long long INF= 1e17;
fill_n(dp, N + 2, INF), dp[0]= 0;
auto w= [&](int i, int j) { return (S[i] - S[j]) * (S[i] - S[j]); };
for (int l= N; l--;) {
auto f= [&](int i, int j) { return dp[j] + w(i - 1, j); };
LiChaoTree lct(f, 1, N + 2);
auto tree= lct.make_tree<MINIMIZE>();
long long ndp[N + 2];
for (int i= 1; i < N + 2; ++i) {
tree.insert(i - 1);
ndp[i]= tree.query(i).first;
}
ndp[0]= INF;
copy_n(ndp, N + 2, dp);
ans[l]= dp[N + 1];
}
for (int i= 0; i < N; ++i) cout << ans[i] << '\n';
return 0;
}
#line 1 "test/yukicoder/952.LiCT.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/952
// competitive-verifier: TLE 2
// competitive-verifier: MLE 512
#include <iostream>
#include <numeric>
#line 2 "src/Optimization/LiChaoTree.hpp"
#include <limits>
#include <algorithm>
#include <vector>
#include <tuple>
#include <cassert>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
static std::false_type check(...);
static C *m;
static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 9 "src/Optimization/LiChaoTree.hpp"
template <class F, class T> class LiChaoTree {};
template <class F, class T, class... Prms> class LiChaoTree<F, std::tuple<T, Prms...>> {
using R= result_type_t<F>;
F f;
const T LB, UB;
std::vector<std::tuple<Prms...>> ps;
template <MinMaxEnum sgn, bool persistent> class LiChaoTreeInterface {
LiChaoTree *ins;
struct Node {
int id= -1;
Node *ch[2]= {nullptr, nullptr};
} *root;
inline R eval(int id, T x) const { return std::apply(ins->f, std::tuple_cat(std::make_tuple(x), ins->ps[id])); }
static inline bool cmp(const R &p, const R &n, int pi, int ni) {
if constexpr (sgn == MINIMIZE) return p > n || (p == n && pi > ni);
else return p < n || (p == n && pi > ni);
}
inline bool cmp(T x, int pi, int ni) const {
if (ni == -1) return false;
if (pi == -1) return true;
return cmp(eval(pi, x), eval(ni, x), pi, ni);
}
static inline T ub(T r) {
if constexpr (std::is_floating_point_v<T>) return r;
else return r - 1;
}
inline void addl(Node *&t, int id, T xl, T xr) {
if (!t) return t= new Node{id}, void();
bool bl= cmp(xl, t->id, id), br= cmp(ub(xr), t->id, id);
if (!bl && !br) return;
if constexpr (persistent) t= new Node(*t);
if (bl && br) return t->id= id, void();
T xm= (xl + xr) / 2;
if (cmp(xm, t->id, id)) std::swap(t->id, id), bl= !bl;
if constexpr (std::is_floating_point_v<T>)
if (xr - xl < 1e-9) return;
bl ? addl(t->ch[0], id, xl, xm) : addl(t->ch[1], id, xm, xr);
}
inline void adds(Node *&t, int id, T l, T r, T xl, T xr) {
if (r <= xl || xr <= l) return;
if (l <= xl && xr <= r) return addl(t, id, xl, xr);
if (!t) t= new Node;
else if constexpr (persistent) t= new Node(*t);
T xm= (xl + xr) / 2;
adds(t->ch[0], id, l, r, xl, xm), adds(t->ch[1], id, l, r, xm, xr);
}
inline std::pair<R, int> query(const Node *t, T x, T xl, T xr) const {
if (!t) return {R(), -1};
T xm= (xl + xr) / 2;
auto b= x < xm ? query(t->ch[0], x, xl, xm) : query(t->ch[1], x, xm, xr);
if (t->id == -1) return b;
R a= eval(t->id, x);
return b.second != -1 && cmp(a, b.first, t->id, b.second) ? b : std::make_pair(a, t->id);
}
public:
LiChaoTreeInterface()= default;
LiChaoTreeInterface(LiChaoTree *ins): ins(ins), root(nullptr) {}
void insert(const Prms &...args) { ins->ps.emplace_back(args...), addl(root, ins->ps.size() - 1, ins->LB, ins->UB); }
// [l, r)
void insert(const Prms &...args, T l, T r) {
l= std::max(l, ins->LB), r= std::min(r, ins->UB);
if (l < r) ins->ps.emplace_back(args...), adds(root, ins->ps.size() - 1, l, r, ins->LB, ins->UB);
}
// [l, UB)
void insert(const Prms &...args, T l) { insert(args..., l, ins->UB); }
std::pair<R, int> query(T x) const { return assert(ins->LB <= x && x < ins->UB), query(root, x, ins->LB, ins->UB); }
const std::tuple<Prms...> ¶ms(int id) const { return ins->ps[id]; }
};
public:
LiChaoTree(const F &f, T LB= -2e9, T UB= 2e9): f(f), LB(LB), UB(UB) {}
template <MinMaxEnum sgn= MINIMIZE, bool persistent= false> LiChaoTreeInterface<sgn, persistent> make_tree() { return this; }
};
template <class F, class T, class U> LiChaoTree(F, T, U) -> LiChaoTree<F, argument_type_t<F>>;
template <class F, class T> LiChaoTree(F, T) -> LiChaoTree<F, argument_type_t<F>>;
template <class F> LiChaoTree(F) -> LiChaoTree<F, argument_type_t<F>>;
#line 7 "test/yukicoder/952.LiCT.test.cpp"
using namespace std;
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N;
cin >> N;
int A[N];
for (int i= 0; i < N; ++i) cin >> A[i];
long long S[N + 1], dp[N + 2], ans[N];
S[0]= 0;
for (int i= 0; i < N; ++i) S[i + 1]= S[i] + A[i];
static constexpr long long INF= 1e17;
fill_n(dp, N + 2, INF), dp[0]= 0;
auto w= [&](int i, int j) { return (S[i] - S[j]) * (S[i] - S[j]); };
for (int l= N; l--;) {
auto f= [&](int i, int j) { return dp[j] + w(i - 1, j); };
LiChaoTree lct(f, 1, N + 2);
auto tree= lct.make_tree<MINIMIZE>();
long long ndp[N + 2];
for (int i= 1; i < N + 2; ++i) {
tree.insert(i - 1);
ndp[i]= tree.query(i).first;
}
ndp[0]= INF;
copy_n(ndp, N + 2, dp);
ans[l]= dp[N + 1];
}
for (int i= 0; i < N; ++i) cout << ans[i] << '\n';
return 0;
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++-13 | sample_1 |
![]() |
7 ms | 4 MB |
g++-13 | sample_2 |
![]() |
6 ms | 3 MB |
g++-13 | sample_3 |
![]() |
6 ms | 4 MB |
g++-13 | testcase_1.txt |
![]() |
859 ms | 167 MB |
g++-13 | testcase_10.txt |
![]() |
473 ms | 96 MB |
g++-13 | testcase_11.txt |
![]() |
500 ms | 101 MB |
g++-13 | testcase_12.txt |
![]() |
94 ms | 25 MB |
g++-13 | testcase_13.txt |
![]() |
760 ms | 148 MB |
g++-13 | testcase_14.txt |
![]() |
129 ms | 32 MB |
g++-13 | testcase_15.txt |
![]() |
95 ms | 25 MB |
g++-13 | testcase_16.txt |
![]() |
187 ms | 43 MB |
g++-13 | testcase_17.txt |
![]() |
8 ms | 4 MB |
g++-13 | testcase_18.txt |
![]() |
8 ms | 4 MB |
g++-13 | testcase_19.txt |
![]() |
424 ms | 87 MB |
g++-13 | testcase_2.txt |
![]() |
840 ms | 164 MB |
g++-13 | testcase_20.txt |
![]() |
73 ms | 20 MB |
g++-13 | testcase_3.txt |
![]() |
673 ms | 132 MB |
g++-13 | testcase_4.txt |
![]() |
1041 ms | 200 MB |
g++-13 | testcase_5.txt |
![]() |
320 ms | 68 MB |
g++-13 | testcase_6.txt |
![]() |
1191 ms | 226 MB |
g++-13 | testcase_7.txt |
![]() |
1204 ms | 229 MB |
g++-13 | testcase_8.txt |
![]() |
444 ms | 91 MB |
g++-13 | testcase_9.txt |
![]() |
7 ms | 4 MB |
g++-13 | testcase_tester_01.txt |
![]() |
8 ms | 4 MB |
g++-13 | testcase_tester_02.txt |
![]() |
28 ms | 10 MB |
g++-13 | testcase_tester_03.txt |
![]() |
1382 ms | 284 MB |
clang++-18 | sample_1 |
![]() |
6 ms | 4 MB |
clang++-18 | sample_2 |
![]() |
5 ms | 4 MB |
clang++-18 | sample_3 |
![]() |
5 ms | 4 MB |
clang++-18 | testcase_1.txt |
![]() |
893 ms | 167 MB |
clang++-18 | testcase_10.txt |
![]() |
488 ms | 96 MB |
clang++-18 | testcase_11.txt |
![]() |
512 ms | 101 MB |
clang++-18 | testcase_12.txt |
![]() |
97 ms | 25 MB |
clang++-18 | testcase_13.txt |
![]() |
785 ms | 148 MB |
clang++-18 | testcase_14.txt |
![]() |
130 ms | 32 MB |
clang++-18 | testcase_15.txt |
![]() |
95 ms | 25 MB |
clang++-18 | testcase_16.txt |
![]() |
191 ms | 43 MB |
clang++-18 | testcase_17.txt |
![]() |
7 ms | 4 MB |
clang++-18 | testcase_18.txt |
![]() |
7 ms | 4 MB |
clang++-18 | testcase_19.txt |
![]() |
434 ms | 87 MB |
clang++-18 | testcase_2.txt |
![]() |
864 ms | 164 MB |
clang++-18 | testcase_20.txt |
![]() |
73 ms | 20 MB |
clang++-18 | testcase_3.txt |
![]() |
696 ms | 132 MB |
clang++-18 | testcase_4.txt |
![]() |
1074 ms | 199 MB |
clang++-18 | testcase_5.txt |
![]() |
327 ms | 68 MB |
clang++-18 | testcase_6.txt |
![]() |
1233 ms | 226 MB |
clang++-18 | testcase_7.txt |
![]() |
1256 ms | 229 MB |
clang++-18 | testcase_8.txt |
![]() |
455 ms | 91 MB |
clang++-18 | testcase_9.txt |
![]() |
7 ms | 4 MB |
clang++-18 | testcase_tester_01.txt |
![]() |
8 ms | 5 MB |
clang++-18 | testcase_tester_02.txt |
![]() |
29 ms | 10 MB |
clang++-18 | testcase_tester_03.txt |
![]() |
1410 ms | 284 MB |