#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOD(i, r, l) for (int i = (r); i >= _l; --i)
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define Konosuba tuple<int , int , int, int>
#define fi first
#define se second
const int NMAX = 3005;
const int INF = 4e18;
int n, k;
int a[NMAX];
int prefixsum[NMAX];
int dp[NMAX][NMAX];
int whereCut[NMAX][NMAX];
bool isUseless(const pii &L1, const pii &L2, const pii &L3) {
// Kiểm tra xem L2 có bị L3 làm vô dụng không
// (c2-c1)*(m2-m3) >= (c3-c2)*(m1-m2)
long long m1=L1.fi, c1=L1.se;
long long m2=L2.fi, c2=L2.se;
long long m3=L3.fi, c3=L3.se;
return (c2 - c1) * (m2 - m3) >= (c3 - c2) * (m1 - m2);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
FOR(i, 1, n) {
cin >> a[i];
prefixsum[i] = prefixsum[i-1] + a[i];
}
// --- Base case: 1 đoạn ---
FOR(i, 1, n) {
dp[i][1] = prefixsum[i] * (prefixsum[n] - prefixsum[i]);
}
// --- DP layers j = 2..k ---
FOR(j, 2, k) {
deque<int> dq;
dq.push_back(j-1);
FOR(i, j, n) {
// 1) Lấy dòng tốt nhất cho i
while (dq.size() >= 2) {
int x = dq[0], y = dq[1];
long long v1 = dp[x][j-1]
- prefixsum[x] * (prefixsum[n] - prefixsum[i]);
long long v2 = dp[y][j-1]
- prefixsum[y] * (prefixsum[n] - prefixsum[i]);
if (v2 >= v1) dq.pop_front();
else break;
}
int best = dq.front();
dp[i][j] = dp[best][j-1]
+ (prefixsum[i] - prefixsum[best])
* (prefixsum[n] - prefixsum[i]);
whereCut[j][i] = best;
// 2) Thêm dòng mới tương ứng với điểm cắt i
pii newLine = { -prefixsum[i], dp[i][j-1] };
// – Xóa nếu slope trùng và intercept nhỏ hơn
if (!dq.empty()) {
int last = dq.back();
if (-prefixsum[last] == newLine.fi) {
if (dp[last][j-1] >= newLine.se)
continue;
else
dq.pop_back();
}
}
// – Duy trì tính lồi: pop khi L2 vô dụng giữa L1 & newLine
while (dq.size() >= 2) {
int u = dq[dq.size()-2], v = dq.back();
pii L1 = { -prefixsum[u], dp[u][j-1] };
pii L2 = { -prefixsum[v], dp[v][j-1] };
if (isUseless(L1, L2, newLine))
dq.pop_back();
else
break;
}
dq.push_back(i);
}
}
// --- Tìm kết quả và truy vết ---
long long answer = -INF;
int idx = -1;
FOR(i, k, n) {
if (dp[i][k] > answer) {
answer = dp[i][k];
idx = i;
}
}
cout << answer << endl;
vector<int> cuts;
for (int j = k; j >= 1; --j) {
cuts.pb(idx);
idx = whereCut[j][idx];
}
reverse(cuts.begin(), cuts.end());
for (int x : cuts) cout << x << ' ';
cout << endl;
return 0;
}
