#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; int n,k; lint dp[100005][205],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=0; t<=k; t++) { convexHull.clear(); for (int i=1; i<=n; i++) { pi x = convexHull.query(a[i]); track[i][t] = x.second; dp[i][t%2] = x.first + a[i] * (a[n] - a[i]); convexHull.insert(a[i],dp[i][!(t%2)] - a[n]*a[i], i); } } 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(); } }