#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG_INF = (ll)-9e18;
const ll INF = (ll)9e18;
int n, k;
vector<ll> a, pre;
// parentPacked: lưu (k+2) x (n+1) entries, mỗi entry 3 bytes (little-endian)
vector<unsigned char> parentPacked;
inline void set_parent(int layer, int idx, int val){
size_t pos = ((size_t)layer * (n + 1) + idx) * 3;
parentPacked[pos] = (unsigned char)(val & 0xFF);
parentPacked[pos + 1] = (unsigned char)((val >> 8) & 0xFF);
parentPacked[pos + 2] = (unsigned char)((val >> 16) & 0xFF);
}
inline int get_parent(int layer, int idx){
size_t pos = ((size_t)layer * (n + 1) + idx) * 3;
int v = parentPacked[pos] | (parentPacked[pos + 1] << 8) | (parentPacked[pos + 2] << 16);
return v;
}
struct line{
long long a, b;
mutable long double p;
int id;
bool operator < (const line& other) const {
if (other.a == (long long)1e18 && other.b == (long long)1e18)
return p < other.p;
return a < other.a || (a == other.a && b < other.b);
}
};
struct LINE_CONTAINER {
multiset<line> ms;
inline bool del(multiset<line>::iterator x, multiset<line>::iterator y){
if (y == ms.end()){
x->p = 1e18;
return false;
}
if (x->a == y->a){
x->p = (x->b >= y->b) ? 1e18 : -1e18;
} else {
x->p = (long double)(y->b - x->b) / (long double)(x->a - y->a);
}
return x->p >= y->p;
}
inline void update(long long a, long long b, int i){
auto x = ms.insert({a,b,0.0L,i});
auto y = next(x);
while (del(x,y)) y = ms.erase(y);
if (x != ms.begin()){
y = prev(x);
if (del(y,x)) ms.erase(x);
} else y = x;
while (y != ms.begin()){
x = prev(y);
if (del(x,y)){
del(x, ms.erase(y));
y = x;
} else break;
}
}
inline pair<long long,int> get(long long x){
auto it = ms.lower_bound({(long long)1e18, (long long)1e18, (long double)x, 0});
if (it == ms.end()) return {NEG_INF, 0};
return { it->a * x + it->b, it->id };
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> n >> k)) return 0;
a.assign(n+1,0);
pre.assign(n+1,0);
for (int i = 1; i <= n; ++i){ cin >> a[i]; pre[i] = pre[i-1] + a[i]; }
// allocate packed parents: (k+2) layers * (n+1) entries * 3 bytes
parentPacked.assign((size_t)(k + 2) * (n + 1) * 3, 0);
// dp only 2 layers
vector<ll> dp_prev(n+1, INF), dp_cur(n+1, INF);
dp_prev[0] = 0;
for (int c = 1; c <= k + 1; ++c){
LINE_CONTAINER lc;
// insert t=0 if valid
if (dp_prev[0] < INF/4) lc.update(2LL * pre[0], -(dp_prev[0] + pre[0]*pre[0]), 0);
// reset dp_cur
fill(dp_cur.begin(), dp_cur.end(), INF);
for (int i = 1; i <= n; ++i){
auto g = lc.get(pre[i]);
if (g.first != NEG_INF){
ll val = pre[i]*pre[i] - g.first;
if (val < dp_cur[i]){
dp_cur[i] = val;
// store parent t = g.second into packed array
set_parent(c, i, g.second);
}
}
// add line for t = i to be used later
if (dp_prev[i] < INF/4){
ll slope = 2LL * pre[i];
ll intercept = -(dp_prev[i] + pre[i]*pre[i]);
lc.update(slope, intercept, i);
}
}
dp_prev.swap(dp_cur);
}
ll total = pre[n] * pre[n];
ll min_sumsq = dp_prev[n]; // dp[n][k+1]
ll best_points = (total - min_sumsq) / 2;
cout << best_points << '\n';
// backtrack using packed parents
vector<int> cuts;
int cur = n;
int layer = k + 1;
while (layer > 0 && cur > 0){
int prev = get_parent(layer, cur);
if (prev == 0) break;
cuts.push_back(prev);
cur = prev;
--layer;
}
reverse(cuts.begin(), cuts.end());
// print first k cuts (between 1..n-1). (cuts size should be k)
for (size_t i = 0; i < cuts.size() && (int)i < k; ++i){
if (i) cout << ' ';
cout << cuts[i];
}
cout << '\n';
return 0;
}
