DTOGRADA - Sơn tường
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxn=1000010;
var n,res,m:longint;
re,mm,s:int64;
a,st,pos,d,f:array[0..maxn] of longint;
procedure doc;
var i:longint;
begin
read(n,m);
for i:=1 to n do
begin
read(a[i]); re:=re+a[i];
end;
end;
procedure timmin;
var i,l,r:longint;
begin
st[0]:=-1; l:=1; r:=0;
for i:=1 to n do
begin
while (a[i]<=st[r]) and (r>=l) do r:=r-1;
r:=r+1;
st[r]:=a[i];
pos[r]:=i;
while i-pos[l]>m-1 do l:=l+1;
d[i]:=st[l];
end;
end;
procedure tinh;
var i,j:longint;
begin
mm:=m;
res:=1; f[1]:=m;
for i:=m+1 to n do
begin
j:=res-1;
while (j>0) and (d[f[j+1]]<=d[i]) and (f[j]+m>=i) and (d[f[j]]>=d[f[j+1]]) do j:=j-1;
res:=j+2;
f[res]:=i;
end;
s:=mm*d[f[1]];
for i:=2 to res do
begin
s:=s+(f[i]-f[i-1])*d[f[i]];
j:=d[f[i]]-d[f[i-1]];
if j>0 then s:=s+(mm-f[i]+f[i-1])*j;
end;
writeln(re-s);
writeln(res);
end;
begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
doc;
timmin;
tinh;
close(input); close(output);
end.