| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 259041 | KoD | Split the sequence (APIO14_sequence) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#line 1 "main.cpp"
/**
* @title Template
*/
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/chmin_chmax.cpp"
template <class T, class U>
constexpr bool chmin(T &lhs, const U &rhs) {
if (lhs > rhs) {
lhs = rhs;
return true;
}
return false;
}
template <class T, class U>
constexpr bool chmax(T &lhs, const U &rhs) {
if (lhs < rhs) {
lhs = rhs;
return true;
}
return false;
}
/**
* @title Chmin/Chmax
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"
#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"
class range {
public:
class iterator {
private:
int64_t M_position;
public:
constexpr iterator(int64_t position) noexcept: M_position(position) { }
constexpr void operator ++ () noexcept { ++M_position; }
constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
constexpr int64_t operator * () const noexcept { return M_position; }
};
class reverse_iterator {
private:
int64_t M_position;
public:
constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { }
constexpr void operator ++ () noexcept { --M_position; }
constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
constexpr int64_t operator * () const noexcept { return M_position; }
};
private:
const iterator M_first, M_last;
public:
constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
constexpr iterator begin() const noexcept { return M_first; }
constexpr iterator end() const noexcept { return M_last; }
constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); }
constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); }
};
/**
* @title Range
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"
#include <type_traits>
#include <iterator>
#line 6 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"
template <class T>
class rev_impl {
public:
using iterator = typename std::decay<T>::type::reverse_iterator;
private:
const iterator M_begin;
const iterator M_end;
public:
constexpr rev_impl(T &&cont) noexcept: M_begin(std::rbegin(cont)), M_end(std::rend(cont)) { }
constexpr iterator begin() const noexcept { return M_begin; }
constexpr iterator end() const noexcept { return M_end; }
};
template <class T>
constexpr decltype(auto) rev(T &&cont) {
return rev_impl<T>(std::forward<T>(cont));
}
/**
* @title Reverser
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/multi_vec.cpp"
#include <cstddef>
#line 5 "/Users/kodamankod/Desktop/Programming/Library/other/multi_vec.cpp"
#include <type_traits>
template <class T, size_t N, size_t I = 0>
decltype(auto) multi_vec(const size_t (&)[N], typename std::enable_if<(I == N), const T&>::type value = T{}) {
return value;
}
template <class T, size_t N, size_t I = 0>
decltype(auto) multi_vec(const size_t (&list)[N], typename std::enable_if<(I != N), const T&>::type value = T{}) {
return std::vector(list[I], multi_vec<T, N, I + 1>(list, value));
}
/**
* @title Multi-Dimensional Vector
*/
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"
#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"
template <class Func>
struct fix_point_impl: private Func {
explicit constexpr fix_point_impl(Func &&func): Func(std::forward<Func>(func)) { }
template <class... Args>
constexpr decltype(auto) operator () (Args &&... args) const {
return Func::operator()(*this, std::forward<Args>(args)...);
}
};
template <class Func>
constexpr decltype(auto) fix_point(Func &&func) {
return fix_point_impl<Func>(std::forward<Func>(func));
}
/**
* @title Lambda Recursion
*/
#line 19 "main.cpp"
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;
int main() {
i32 N, K;
std::cin >> N >> K;
assert(N <= 50);
std::vector<i32> A(N);
for (auto &x: A) {
std::cin >> x;
}
std::vector<i32> sum(N + 1);
for (auto i: range(0, N)) {
sum[i + 1] = sum[i] + A[i];
}
auto dp = multi_vec<i64>({ N, N + 1, K + 1 }, -inf64);
for (auto l: range(0, N)) {
for (auto r: range(l + 1, N + 1)) {
dp[l][r][0] = 0;
}
}
for (auto len: range(2, N + 1)) {
for (auto l: range(0, N - len + 1)) {
auto r = l + len;
for (auto m: range(l + 1, r)) {
for (auto s: range(0, std::min<i64>(K, m - l))) {
for (auto t: range(0, std::min<i64>(K - s, r - m))) {
chmax(dp[l][r][s + t + 1], dp[l][m][s] + dp[m][r][t] + (sum[m] - sum[l]) * (sum[r] - sum[m]));
}
}
}
}
}
std::cout << dp[0][N][K] << '\n';
std::vector<i32> step;
fix_point([&](auto dfs, i32 l, i32 r, i32 k) {
if (k == 0) return;
for (auto m: range(l + 1, r)) {
for (auto s: range(0, std::min<i64>(k, m - l))) {
if (dp[l][r][k] == dp[l][m][s] + dp[m][r][k - s - 1] + (sum[m] - sum[l]) * (sum[r] - sum[m])) {
step.push_back(m);
dfs(l, m, s);
dfs(m, r, k - s - 1);
return;
}
}
}
})(0, N, K);
for (auto i: range(0, K)) {
std::cout << step[i] << (i + 1 == K ? '\n' : ' ');
}
return 0;
}