#ifdef EZ
#include "./ez/ez.h"
#else
#include <bits/stdc++.h>
#endif
#define mp make_pair
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
void EZinit() {
#ifndef EZ
//cin.tie(0)->sync_with_stdio(0);
#else
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
}
/*
vom afla raspunsul secvential: j=1,2,..k secvente. pt j=1 folosim cea mai mare subsecventa initial.
pt a trece de la j-1 la j, ori folosim o noua subsecventa, ori
spargem o subsecventa deja folosita (scoatem sub-subsecventa de suma MINIMA).
*/
void get(int &x)
{
static char c;
static bool neg;
while (!isdigit(c = getchar_unlocked()) && c != '-');
if (c == '-') neg = 1, x = 0;
else neg = 0, x = c-'0';
while (isdigit(c = getchar_unlocked())) x = x*10 + c-'0';
if (neg) x *= -1;
}
int n, k;
int v[300001];
ll sp[600001];
#define sum(x,y) (sp[y]-sp[x-1])
struct alexaint {
int x, y, xp, xs;
};
const int ainth = 19;
const int aintlim = 1<<ainth;
alexaint aintmi[2*aintlim], aintma[2*aintlim];
bool minmx; alexaint* aint;
inline alexaint combine(alexaint &A, alexaint &B, int st, int dr)
{
alexaint Q; ll a, b, c;
a = sum(st, A.xp); b = sum(st, B.xp);
Q.xp = (((minmx) ? (a<=b) : (a>=b)) ? A.xp : B.xp);
a = sum(B.xs, dr); b = sum(A.xs, dr);
Q.xs = (((minmx) ? (a<=b) : (a>=b)) ? B.xs : A.xs);
a = sum(A.x, A.y); b = sum(B.x, B.y); c = sum(A.xs, B.xp);
if (minmx)
{
if (a <= min(b,c)) Q.x = A.x, Q.y = A.y;
else if (b <= min(a,c)) Q.x = B.x, Q.y = B.y;
else Q.x = A.xs, Q.y = B.xp;
}
else
{
if (a >= max(b,c)) Q.x = A.x, Q.y = A.y;
else if (b >= max(a,c)) Q.x = B.x, Q.y = B.y;
else Q.x = A.xs, Q.y = B.xp;
}
return Q;
}
void build(int nod = 1, int st = 1, int dr = aintlim)
{
if (st == dr) return (void) (aintma[nod] = aintmi[nod] = {st, st, st, st});
int mj = st+dr >> 1;
build(nod*2, st, mj);
build(nod*2+1, mj+1, dr);
minmx = false;
aintma[nod] = combine(aintma[nod*2], aintma[nod*2+1], st, dr);
minmx = true;
aintmi[nod] = combine(aintmi[nod*2], aintmi[nod*2+1], st, dr);
}
alexaint ansst, ansdr;
inline alexaint que(int qst, int qdr)
{
int QST = qst, QDR = qdr;
if (qst == qdr) return {qst, qst, qst, qst};
ansst.x = ansst.y = ansst.xp = ansst.xs = qst;
ansdr.x = ansdr.y = ansdr.xp = ansdr.xs = qdr;
qst += aintlim-1;
qdr += aintlim-1;
qst++; qdr--;
for (; qst <= qdr; qst >>= 1, qdr >>= 1)
{
if (qst&1)
ansst = combine(ansst, aint[qst], QST, (qst+1-(1<<__lg(qst)))*(1<<ainth-__lg(qst))),
qst++;
if (!(qdr&1))
ansdr = combine(aint[qdr], ansdr, 1 + (qdr-(1<<__lg(qdr)))*(1<<ainth-__lg(qdr)), QDR),
qdr--;
}
return combine(ansst, ansdr, QST, QDR);
}
struct alexmax {
int fi, se;
bool operator<(const alexmax &B) const
{
minmx = false; aint = aintma;
auto Xq = que(fi, se);
int X1 = Xq.x, X2 = Xq.y;
auto Yq = que(B.fi, B.se);
int Y1 = Yq.x, Y2 = Yq.y;
return sum(X1,X2) < sum(Y1,Y2);
}
};
struct alexmin {
int fi, se;
bool operator<(const alexmin &B) const
{
minmx = true; aint = aintmi;
auto Xq = que(fi, se);
int X1 = Xq.x, X2 = Xq.y;
auto Yq = que(B.fi, B.se);
int Y1 = Yq.x, Y2 = Yq.y;
return sum(X1,X2) > sum(Y1,Y2);
}
};
int main()
{
EZinit();
get(n); get(k);
for (int i = 1; i <= n; ++i) get(v[i]), sp[i] = sp[i-1] + v[i];
build();
ll ans = 0;
priority_queue<alexmin> ivuse;
priority_queue<alexmax> ivno;
ivno.push({1, n});
for (int j = 1; j <= k; ++j)
{
// ce putem scoate
ll Ss = LLONG_MAX; int xs, ys, Xs, Ys;
if (!ivuse.empty())
{
xs = ivuse.top().fi, ys = ivuse.top().se;
minmx = true; aint = aintmi;
auto q = que(xs, ys);
Xs = q.x, Ys = q.y;
Ss = sum(Xs,Ys);
if (-Ss <= 0) ivuse.pop();
}
// ce putem pune
ll Sp = LLONG_MIN; int xp, yp, Xp, Yp;
if (!ivno.empty())
{
xp = ivno.top().fi, yp = ivno.top().se;
minmx = false; aint = aintma;
auto q = que(xp, yp);
Xp = q.x, Yp = q.y;
Sp = sum(Xp,Yp);
if (Sp <= 0) ivno.pop();
}
if (Ss != LLONG_MAX && -Ss >= 1 && (-Ss > Sp || Sp == LLONG_MIN))
{ // scoatem
ivuse.pop();
if (xs != Xs) ivuse.push({xs,Xs-1});
if (ys != Ys) ivuse.push({Ys+1, ys});
ivno.push({Xs,Ys});
ans += -Ss;
}
if (Sp != LLONG_MIN && Sp >= 1 && (Sp >= -Ss || Ss == LLONG_MAX))
{ // punem
ivno.pop();
if (xp != Xp) ivno.push({xp,Xp-1});
if (yp != Yp) ivno.push({Yp+1, yp});
ivuse.push({Xp,Yp});
ans += Sp;
}
}
cout << ans << '\n';
}
