#include <iostream>
#include <vector>
#include <utility>
const long long INF = 1000000000000000ll;
struct ConvexHull {
std::vector<std::pair<long long, long long>> lines;
std::vector<std::pair<long long, long long>> intervals; // inclusive, line[l] is the GOAT for intervals[l].first..intervals[l].second
int ptr = 0;
void push(std::pair<long long, long long> line);
void emplace(long long m, long long c) {push(std::make_pair(m, c));}
long long querymax(long long u, int* sz);
};
std::pair<long long, long long> intersect(std::pair<long long, long long> l1, std::pair<long long, long long> l2) {
if (l1.first == l2.first) return {INF, INF};
long long left = (l2.second - l1.second) / (l1.first - l2.first);
long long right = (l2.second - l1.second - 1) / (l1.first - l2.first) + 1;
return {left, right};
}
long long apply(std::pair<long long, long long> l, long long u) {
return l.first * u + l.second;
}
void ConvexHull::push(std::pair<long long, long long> line) {
if (lines.empty()) {
lines.push_back(line);
intervals.emplace_back(-INF, INF);
}
while (lines.size() - ptr >= 2) {
auto isct = intersect(line, lines[lines.size()-2]);
long long startrange = isct.second;
if (startrange < intervals.back().first) {
lines.pop_back();
intervals.pop_back();
intervals.back().second = isct.first;
} else {
break;
}
}
auto isct = intersect(line, lines.back());
lines.push_back(line);
intervals.emplace_back(isct.second, INF);
}
long long ConvexHull::querymax(long long u, int* sz) {
while (lines.size() - ptr >= 2) {
long long now = apply(lines[ptr], u);
long long next = apply(lines[ptr+1], u);
if (next > now) ++ptr;
else break;
}
*sz = ptr;
return (apply(lines[ptr], u));
}
int main() {
int n, k;
std::cin >> n >> k;
std::vector<long long> v(n);
for (int i = 0; i < n; ++i) std::cin >> v[i];
std::vector<long long> p(n + 1);
for (int i = 1; i <= n; ++i) p[i] = p[i - 1] + v[i - 1];
/*
dp[kk][i] is the best value using kk splits with last one 'at' i
so if we know dp[kk-1] for all i, then we can calculate dp[kk][i] as:
max from prev=0 to prev = i-1 of (dp[kk-1][prev] + (p[i] - p[prev]) * (p.back() - p[i]))
now at each kk we define a family of functions f_prev(u) like so:
f_prev(u) = dp[kk-1][prev] + p[prev]*u
then we can rewrite:
dp[kk][i] = (max from family(p[i] - p[back])) + (p[i]*p.back() - p[i]^2)
note that for each prev, we have a linear function f_prev
*/
std::vector<std::vector<long long>> dp(k+2, std::vector<long long>(n+1));
std::vector<std::vector<int>> bestfrom(k+2, std::vector<int>(n+1));
/*
when kk=0, it must be that we can get no score
*/
for (int i = 0; i <= n; ++i) dp[0][i] = 0;
/*
when i = 0 but kk > 0 then we cannot even do anything, not even score 0
*/
for (int kk = 1; kk <= k+1; ++kk) dp[kk][0] = -INF;
for (int kk = 1; kk <= k+1; ++kk) {
ConvexHull hull;
hull.emplace(p[0], dp[kk-1][0]);
for (int i = 1; i <= n; ++i) {
dp[kk][i] = hull.querymax(p[i] - p.back(), &bestfrom[kk][i]) + p[i] * (p.back() - p[i]);
hull.emplace(p[i], dp[kk-1][i]);
}
}
std::cout << dp[k+1][n] << '\n';
int cur = bestfrom[k+1][n];
while (k) {
std::cout << cur << " \n"[k==1];
cur = bestfrom[k][cur];
--k;
}
}
