juice.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 93 行

{
PROB:juice
LANG:PASCAL
}

program juice;
const
  maxsize=300;
  dx:array[1..4]of shortint=(0,0,1,-1);
  dy:array[1..4]of shortint=(1,-1,0,0);
type
  coord=record x,y:word;end;
var
  a,b:array[1..maxsize,1..maxsize]of longint;
  h:array[1..sqr(maxsize)]of coord;
  n,m,i,j,hs,level:longint;
  sum:qword;
procedure insheap(u,v:word);
  var
    p,f:longint;
  begin
    b[u,v]:=a[u,v];
    inc(hs);p:=hs;
    while p>1 do begin
      f:=p shr 1;
      if a[u,v]>=a[h[f].x,h[f].y] then break;
      h[p]:=h[f];p:=f;
    end;
    with h[p] do begin x:=u;y:=v;end;
  end;
procedure pop(var u,v:longint);
  var
    p,l,r,s,t:longint;
  begin
    with h[1] do begin u:=x;v:=y;end;
    with h[hs] do begin s:=x;t:=y;end;dec(hs);
    p:=1;
    repeat
      l:=p*2;r:=l+1;
      if l>hs then
        break
      else if (l<hs) and (a[h[r].x,h[r].y]<a[s,t]) and (a[h[r].x,h[r].y]<a[h[l].x,h[l].y]) then begin
        h[p]:=h[r];p:=r;
      end
      else if (a[h[l].x,h[l].y]<a[s,t]) then begin
        h[p]:=h[l];p:=l;
      end
      else
        break;
    until false;
    with h[p] do begin x:=s;y:=t;end;
  end;
procedure floodfill(u,v:word);
  var
    d,p,q:word;
  begin
    for d:=1 to 4 do begin
      p:=u+dx[d];q:=v+dy[d];
      if (p>1) and (p<m) and (q>1) and (q<n) and (b[p,q]=0) then
        if a[p,q]>level then
          insheap(p,q)
        else begin
          b[p,q]:=level;floodfill(p,q);
        end;
    end;
  end;
begin
  assign(input,'juice.in');reset(input);
  assign(output,'juice.out');rewrite(output);

  read(n,m);
  for i:=1 to m do
    for j:=1 to n do
      read(a[i,j]);

  fillchar(b,sizeof(b),0);hs:=0;
  for i:=1 to m do begin insheap(i,1);insheap(i,n);end;
  for j:=2 to n-1 do begin insheap(1,j);insheap(m,j);end;

  repeat
    pop(i,j);level:=a[i,j];
    floodfill(i,j);
  until hs=0;

  sum:=0;
  for i:=1 to m do
    for j:=1 to n do
      inc(sum,b[i,j]-a[i,j]);
  writeln(sum);

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