记录编号	24667	评测结果	AAAAAAAAAT
题目名称	山顶问题	最终得分	90
用户昵称	ybh	是否通过	未通过
代码语言	Pascal	运行时间	1.016 s
提交时间	2011-04-13 22:04:52	内存使用	1.63 MiB

program peaks;
var
  h,q:array[-1..100010] of longint;
  sum:array[-1..100010] of int64;
  n,k,i,j,t,last,k1,p,l,r,minl,minr,minh,mini,hh:longint;
  bool:boolean;
  ans,temp,min:int64;

begin
  assign(input,'peaks.in');
  reset(input);
  assign(output,'peaks.out');
  rewrite(output);

  readln(n,k);
  sum[0]:=0;
  for i:=1 to n do
  begin
    read(h[i]);
    sum[i]:=sum[i-1]+h[i];
  end;
  h[0]:=0;
  h[n+1]:=0;

  last:=0;
  k1:=0;
  for i:=1 to n do
  begin
    if (last<h[i]) and (h[i]>h[i+1]) then
    begin
      inc(k1);
      q[k1]:=i;
    end;
    if h[i]<>h[i+1] then last:=h[i];
  end;
  t:=k1;

  ans:=0;
  for p:=1 to k1-k do
  begin
    min:=-1;
    for i:=1 to t do
    begin
      if q[i]=0 then continue;
      j:=q[i];
      bool:=true;
      while bool do
      begin
        if ((last>h[j]) and (h[j]<h[j+1])) or (j=n+1) then
        begin
          bool:=false;
          r:=j;
        end;
        if h[j]<>h[j+1] then last:=h[j];
        j:=j+1;
      end;

      j:=q[i];
      bool:=true;
      while bool do
      begin
        if ((last>h[j]) and (h[j]<h[j-1])) or (j=0) then
        begin
          bool:=false;
          l:=j;
        end;
        if h[j]<>h[j-1] then last:=h[j];
        j:=j-1;
      end;

      if h[l]>h[r] then
      begin
        hh:=h[l];
        while h[r-1]<h[l] do
          dec(r);
      end
      else
      begin
        hh:=h[r];
        while h[l+1]<h[r] do
          inc(l);
      end;

      temp:=sum[r-1]-sum[l]-hh*(r-l-1);
      if (temp<min) or (min=-1) then
      begin
        min:=temp;
        minl:=l;
        minr:=r;
        minh:=hh;
        mini:=i;
      end;
    end;

    ans:=ans+min;
    q[mini]:=0;

    for i:=minl+1 to minr-1 do
    begin
      h[i]:=minh;
      sum[i]:=sum[i-1]+h[i];
    end;

    for i:=minr to n do
      sum[i]:=sum[i-1]+h[i];
  end;

  writeln(ans);

  close(input);
  close(output);
end.