#include <iostream> #include <deque> using namespace std; typedef long long llong; const int MAXN = 1e5 + 10; const int MAXK = 2e2 + 10; struct Line { llong k, m, idx; Line(){}; Line(llong k, llong m, llong idx) { this->k = k; this->m = m; this->idx = idx; } long double intersect(Line &other) { return (long double)(m - other.m) / (long double)(other.k - k); } llong eval(llong x) { return k * x + m; } }; struct CHT { deque < Line > dq; CHT(){}; void addLine(Line l) { if(!dq.empty() && l.k == dq.back().k) { if(l.m <= dq.back().m) return; dq.pop_back(); } while(dq.size() >= 2 && dq[dq.size() - 1].intersect(dq[dq.size() - 2]) >= dq[dq.size() - 1].intersect(l)) { dq.pop_back(); } dq.push_back(l); } void addLine(llong k, llong m, llong idx) { addLine(Line(k, m, idx)); } pair < llong, int > query(llong x) { while(dq.size() >= 2 && dq[0].intersect(dq[1]) <= x) { dq.pop_front(); } return {dq[0].eval(x), dq[0].idx}; } void clean() { dq.clear(); } }; CHT cht; int n, k; int a[MAXN]; llong pref[MAXN]; llong dp[MAXN][MAXK]; int from[MAXN][MAXK]; void read() { cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> a[i]; } } void precomp() { for(int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + a[i]; } } void solve() { for(int j = 1; j <= k + 1; j++) { cht.clean(); cht.addLine(0, 0, 0); for(int i = 1; i <= n; i++) { pair < llong, int > p = cht.query(pref[i]); dp[i][j] = pref[i] * pref[n] - pref[i] * pref[i] + p.first; from[i][j] = p.second; cht.addLine(pref[i], dp[i][j - 1] - pref[i] * pref[n], i); } } llong ans = dp[n][k + 1]; int idx = from[n][k + 1]; cout << ans << endl; for(int j = k; j >= 1; j--) { cout << idx << " "; idx = from[idx][j]; } cout << endl; } int main() { read(); precomp(); solve(); return 0; }