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.

Download