#include <iostream>
#include <vector>
#include <utility>
const long double INF = 1000000000000000ll;
struct ConvexHull {
std::vector<std::pair<long double, long double>> lines;
std::vector<std::pair<long double, long double>> intervals; // inclusive, line[l] is the GOAT for intervals[l].first..intervals[l].second
std::vector<int> index;
int total = 0;
int ptr = 0;
void push(std::pair<long double, long double> line);
void emplace(long double m, long double c) {push(std::make_pair(m, c));}
long double querymax(long double u, int* sz);
};
std::pair<long double, long double> intersect(std::pair<long double, long double> l1, std::pair<long double, long double> l2) {
if (l1.first == l2.first) return {INF, INF};
long double left = (l2.second - l1.second) / (l1.first - l2.first);
// long double right = (l2.second - l1.second - 1) / (l1.first - l2.first) + 1;
long double right = left;
return {left, right};
}
long double apply(std::pair<long double, long double> l, long double u) {
return l.first * u + l.second;
}
void ConvexHull::push(std::pair<long double, long double> line) {
if (lines.empty()) {
lines.push_back(line);
intervals.emplace_back(-INF, INF);
index.push_back(total++);
return;
}
while (lines.size() - ptr >= 2) {
auto isct = intersect(line, lines[lines.size()-2]);
long double startrange = isct.second;
if (startrange < intervals.back().first) {
lines.pop_back();
intervals.pop_back();
intervals.back().second = isct.first;
index.pop_back();
} else {
break;
}
}
auto isct = intersect(line, lines.back());
lines.push_back(line);
intervals.emplace_back(isct.second, INF);
index.push_back(total++);
}
long double ConvexHull::querymax(long double u, int* sz) {
while (lines.size() - ptr >= 2) {
long double now = apply(lines[ptr], u);
long double next = apply(lines[ptr+1], u);
if (next > now) ++ptr;
else break;
}
*sz = index[ptr];
return (apply(lines[ptr], u));
}
int main() {
int n, k;
std::cin >> n >> k;
std::vector<long double> v(n);
for (int i = 0; i < n; ++i) std::cin >> v[i];
std::vector<long double> 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
*/
/*
we make kk implicit using inline dp
*/
std::vector<long double> dp(n+1);
std::vector<long double> newdp(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[i] = 0;
for (int kk = 1; kk <= k+1; ++kk) {
/*
when i = 0 but kk > 0 then we cannot even do anything, not even score 0
*/
newdp[0] = -INF;
ConvexHull hull;
hull.emplace(p[0], dp[0]);
for (int i = 1; i <= n; ++i) {
newdp[i] = hull.querymax(p[i] - p.back(), &bestfrom[kk][i]) + p[i] * (p.back() - p[i]);
hull.emplace(p[i], dp[i]);
}
dp = newdp;
}
std::cout << (long long)(dp[n]) << '\n';
int cur = bestfrom[k+1][n];
while (k) {
std::cout << cur << " \n"[k==1];
cur = bestfrom[k][cur];
--k;
}
}
