#include <cstdio> #include <utility> #include <vector> using namespace std; typedef long long lint; typedef pair<lint, int> pi; struct cht{ int s,e; lint la[100005],lb[100005]; int label[100005]; double cross(int a, int b){return (double)(lb[b]-lb[a])/(la[a]-la[b]);} void insert(lint p, lint q, int piv){ la[e] = p; lb[e] = q; label[e] = piv; while(e>1 && cross(e-1,e-2) < cross(e,e-1)){ la[e-1] = la[e]; lb[e-1] = lb[e]; label[e-1] = label[e]; e--; } e++; } pi query(lint x){ while(s+1<e && cross(s,s+1) > x) s++; return pi(la[s]*x+lb[s],label[s]); } void clear(){s = e = 0;} }convexHull[2]; int n,k; lint dp[100005][2],a[100005]; int track[100005][205]; int main(){ int t; scanf("%d %d",&n,&k); for (int i=0; i<n; i++) { scanf("%d",&t); a[i+1] = a[i] + t; } for (int i=1; i<=n; i++) { dp[i][0] = (a[n] - a[i])*(a[i]); } for (int t=1; t<=k; t++) { for (int i=t; i<=n; i++) { long long res = -1e9; for (int j=t; j<i; j++) { lint piv = dp[j][!(t%2)] + (a[i] - a[j]) * (a[n] - a[i]); if(res < piv){ res = piv; track[i][t] = j; } } dp[i][t%2] = res; } } // dependant on J = dp[j][t-1] + a[j-1] (a[n] - a[j-1]) // dependant on I = -a[i-1]a[n] // dependant on IJ = a[i-1] * a[j-1] // lint piv = dp[j][t-1] + (a[j-1] - a[i-1])*(a[n] - a[j-1]); printf("%lld\n",dp[n][k%2]); vector<int> res; int pos1 = n; for(int pos2 = k; pos2 ; pos2--){ res.push_back(track[pos1][pos2]); pos1 = track[pos1][pos2]; } while (!res.empty()) { printf("%d ",res.back()); res.pop_back(); } }