#include <bits/stdc++.h> using namespace std; #define N 100011 #define K 202 #define INF (long long)(1e18 + 36) int n, k, trace[K][N]; long long a[N], dp[2][N]; void calc(int t,int l,int r,int opl,int opr){ if(l > r)return; int mid = (l + r) >> 1; pair<long long, int> best = {-INF * 3, -1}; for(int p = opl; p <= min(mid, opr); p++){ long long C = dp[0][p - 1] + (a[mid] - a[p - 1]) * (a[n] - a[mid]); if(C > best.first){ best = {C, p}; } } dp[1][mid] = best.first; trace[t][mid] = best.second - 1; calc(t, l, mid - 1, opl, best.second); calc(t, mid + 1, r, best.second, opr); } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>k; k++; for(int i = 1; i <= n; i++)cin>>a[i], a[i] += a[i - 1]; for(int j = 0; j <= n; j++) dp[0][j] = dp[1][j] = -INF; dp[0][0] = 0; for(int t = 1; t <= k; t++){ calc(t, 1, n, 1, n); swap(dp[0], dp[1]); dp[1][0] = -INF; } cout<<dp[0][n]<<'\n'; int u = trace[k][n]; k--; vector<int> ans; while(u){ ans.push_back(u); u = trace[k][u]; k--; } reverse(ans.begin(), ans.end()); for(int x : ans)cout<<x<<' '; }