记录编号	97441	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]滑雪场地的难度系数	最终得分	100
用户昵称	zgyzhaoguangyang	是否通过	通过
代码语言	Pascal	运行时间	0.497 s
提交时间	2014-04-18 20:54:13	内存使用	9.72 MiB

var
   f,size,w:array[0..250005] of longint;
   x,y,z:array[0..500005] of longint;
   a:array[0..505,0..505] of longint;
   n,m,t,tot:longint;
   ans:qword;
procedure init;
var i,j:longint;
begin
      readln(n,m,t);
      for i:=1 to n do
        begin
          for j:=1 to m do
            read(a[i,j]);
          readln;
        end;
end;

procedure build;
var i,j:longint;
begin
      tot:=0;
    for i:=1 to n do
       for j:=1 to m-1 do
       begin
         inc(tot);
         x[tot]:=(i-1)*m+j;
         y[tot]:=(i-1)*m+j+1;
         z[tot]:=abs(a[i,j]-a[i,j+1]);
       end;
    for i:=1 to n-1 do
     for j:=1 to m do
     begin
       inc(tot);
       x[tot]:=(i-1)*m+j;
       y[tot]:=i*m+j;
       z[tot]:=abs(a[i,j]-a[i+1,j]);
     end;
end;

procedure qsort(ll,rr:longint);
var i,j,w,t:longint;
begin
    i:=ll;j:=rr;w:=z[(ll+rr)>>1];
    repeat
     while z[i]<w do inc(i);
     while z[j]>w do dec(j);
     if i<=j then
     begin
       t:=x[i];x[i]:=x[j];x[j]:=t;
       t:=y[i];y[i]:=y[j];y[j]:=t;
       t:=z[i];z[i]:=z[j];z[j]:=t;
       inc(i);dec(j);
     end;
    until i>j ;
    if i<rr then qsort(i,rr);
    if ll<j then qsort(ll,j);
end;

function find(xx:longint):longint;
begin
    while f[xx]<>xx do xx:=f[xx];
    exit(xx);
end;

function get(xx:longint):qword;
begin
    while (xx<>f[xx]) and (w[xx]=-1)do xx:=f[xx];
    exit(qword(w[xx]));
end;

procedure mercy(xx,yy,zz:longint);
var tt:longint;
begin
    if size[xx]>size[yy] then begin tt:=xx;xx:=yy;yy:=tt;end;
    f[xx]:=yy;
    if ((size[yy]<t) and (size[xx]+size[yy]>=t)) then w[yy]:=zz
                                                 else
      if ((size[xx]<t) and(size[xx]+size[yy]>=t)) then w[xx]:=zz;
    inc(size[yy],size[xx]);
end;

procedure main;
var i,j,xx,yy:longint;
begin
      build;
      qsort(1,tot);
      for i:=1 to n*m do
      begin
         f[i]:=i;w[i]:=-1;size[i]:=1;
      end;
   for i:=1 to tot do
   begin
     xx:=find(x[i]);
     yy:=find(y[i]);
     if xx<>yy then mercy(xx,yy,z[i]);
   end;
   ans:=0;
   for i:=1 to n do
      begin
        for j:=1 to m do
         begin
           read(xx);
           if xx=1 then inc(ans,get((i-1)*m+j));
         end;
        readln;
      end;
   writeln(ans);
end;

begin
   assign(input,'skilevel.in');reset(input);
   assign(output,'skilevel.out');rewrite(output);
   init;main;
   close(input);close(output);
end.