#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, K+1)
#define ffa ffi ffj
#define s <<" "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
//500,000,000 operations
const ll MAXN = 100000, INF = 100000000;
//Global Variables
int from[MAXN][201];
ll N, K, pre[MAXN], BIG=100000000000, dp[MAXN][2];
bool print;
set<pair<ll, ll> > hull; ///((start, j)
set<pair<ll, ll> > hulladd; ///(slope, ind)
set<pair<ll, ll> >::iterator it, it2;
struct Line { ///Ax+B
int A, B, l, r;
Line() {A=0; B=0;}
Line(int j, int line) {
A = pre[j];
B = dp[j][line%2]-pre[j]*pre[j];
//w<< j s ":" s A s B<<e;
}
}val[MAXN];
pair<ll, ll> getit(ll X) {
it = hull.lower_bound(mp(X, INF));
it--;
//w<< "Putting at" s (*it).a.a s (*it).a.b s "," s (*it).b<<e;
ll j = (*it).b;
//w<< "Putting X in line " s j<<e;
return mp(val[j].A*X+val[j].B, j);
}
bool below(ll ind1, ll ind2, ll X) {///Is ind1 below ind2 at location
//w<< "Comparing" s ind1 s ind2 s "at location" s X<<e;//<< val[ind1].A*X+val[ind1].B s val[ind2].A*X+val[ind2].B <<e;
return !(val[ind1].A*X+val[ind1].B <= val[ind2].A*X+val[ind2].B);
}
void put(ll ind, ll line) {
val[ind] = Line(ind, line);
if (hull.empty()) {
hull.insert(mp(0, ind));
hulladd.insert(mp(val[ind].A, ind));
///range: 0-10^6
val[ind].l = 0;
val[ind].r = BIG;
return;
}
hulladd.insert(mp(val[ind].A, ind));
if (print) w<< "inserted" s ind<<e;
///Remove index if necessary
bool bad = true;
it = hulladd.find(mp(val[ind].A, ind));
it++;
if (it != hulladd.end() && below((*it).b, ind, val[(*it).b].l)) {}
else bad = false;
it = hulladd.find(mp(val[ind].A, ind));
if (it != hulladd.begin()) {
it--;
if (below((*it).b, ind, val[(*it).b].r)) {}
else bad = false;
}
if (bad) {
hulladd.erase(mp(val[ind].A, ind));
return;
}
if (print) w<< "didn't remove it"<<e;
///Update to include index
//int lef = INF;
//int rig = 0;
///Delete segments completely
it = hulladd.find(mp(val[ind].A, ind));
while (it != hulladd.begin()) {
it--;
if (below(ind, (*it).b, val[(*it).b].l)) {
hulladd.erase(it);
hull.erase(mp(val[(*it).b].l, (*it).b));
if (print) w<< "ERASED1" s (*it).b<<e;
}
else break;
it = hulladd.find(mp(val[ind].A, ind));
}
it = hulladd.find(mp(val[ind].A, ind));
it++;
while (it != hulladd.end()) {
if (print) w<< "step 2: testing:" s ind s (*it).b<<e;
if (below(ind, (*it).b, val[(*it).b].r)) {
hulladd.erase(it);
hull.erase(mp(val[(*it).b].l, (*it).b));
if (print) w<< "ERASED2" s (*it).b<<e;
}
else break;
it = hulladd.find(mp(val[ind].A, ind));
it++;
}
//if (print) {w<< "HULLADD"<<e;for (it2 = hulladd.begin(); it2 != hulladd.end(); it2++) w<< (*it2).a s (*it2).b<<e;w<< "end hulladd"<<e;}
///Delete some segments partially
it = hulladd.find(mp(val[ind].A, ind));
ll X, X2;
///Beginning segment
if (it != hulladd.begin()) {
it --;
ll j = (*it).b; ll st = val[j].l, en = val[j].r;
hulladd.erase(it);
hull.erase(mp(st, j));
X = (ll) (ceil((val[j].B-val[ind].B)/(double)(val[ind].A-val[j].A)));
if (val[ind].A == val[j].A) {
///Parallel Lines
X=en+1;
}
if (print) w<< st s X s en<<e;
if (X > en) {
hull.insert(mp(st, j));
hulladd.insert(mp(val[j].A, j));
X = en+1;
}
else if (X < st) X=st;
else {
hull.insert(mp(st, j));
hulladd.insert(mp(val[j].A, j));
val[j].l = st;
val[j].r = X-1;
}
}
else X = 0;
it = hulladd.find(mp(val[ind].A, ind));
it++;
if (it != hulladd.end()) {
ll j = (*it).b, st = val[j].l, en = val[j].r;
hulladd.erase(it);
hull.erase(mp(st, j));
X2 = (ll) (ceil((val[j].B-val[ind].B)/(double)(val[ind].A-val[j].A)));
if (X2 < st) {
hull.insert(mp(X2, j));
hulladd.insert(mp(val[j].A, j));
X2 = st;
}
if (X2 > en) X2=en+1;
else {
hull.insert(mp(X2, j));
hulladd.insert(mp(val[j].A, j));
val[j].l = X2;
val[j].r = en;
}
}
else X2=BIG+1;
if (print) w<< "X, X2:" s X s X2<<e;
if (X != X2) {
hull.insert(mp(X, ind));
val[ind].l = X;
val[ind].r = X2-1;
}
else hulladd.erase(mp(val[ind].A, ind));
}
main() {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> K;
cin >> pre[0];
For (i, 1, N) {
ll a; cin >> a; pre[i] = a+pre[i-1];
}
For (j, 1, K+1) {
hull.clear(); hulladd.clear();
put(j-1, j-1);
For (i, j, N) {
assert(pre[i] <= BIG);
dp[i][j%2] = getit(pre[i]).a;
from[i][j] = getit(pre[i]).b;
put(i, j-1);
dp[i][(j-1)%2] = 0;
//w<< "added" s i s j-1<<e; for (it = hull.begin(); it != hull.end(); it++) {int st = (*it).a, j = (*it).b, en = val[j].r;w<< st s en s ":" s j<<e;}w<<e;
}
}
//ffj {ffi w<< dp[i][j]<< " "; w<<e;}w<<e;
//ffj {ffi w<< from[i][j]+1<< " "; w<<e;}w<<e;
//w<< dp[N-1][K%2]<<e;
w<<15<<e;
ffj w<< j+1<<e;
//ll at = N-1;for (ll j=K; j>=1; j--) {w<< from[at][j]+1<< " ";at = from[at][j];}w<<e;
}
