ac1124.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1124;
const
  maxn=100;
type
  matrix=array[1..maxn,1..maxn]of integer;
  array1=array[1..maxn-1]of longint;
  array2=array[2..maxn]of longint;
var
  a,b:matrix;
  lmax,lmin,umax,umin:array1;
  rmax,rmin,dmax,dmin:array2;
  n,m,i,j,ans,k,smax,smin:longint;
procedure cal(var a,b:matrix;var max1,min1:array1;var max2,min2:array2);
  begin
    fillchar(b,sizeof(b),0);
    for i:=1 to n-1 do begin
      max1[i]:=-maxlongint;min1[i]:=maxlongint;
    end;
    for i:=0 to n-2 do begin
      for j:=1+i to n-1 do begin
        smax:=0;smin:=0;
        for k:=1 to m do begin
          inc(b[j,k],a[j-i,k]);
          inc(smax,b[j,k]);inc(smin,b[j,k]);
          if smax>max1[j] then max1[j]:=smax;if smin<min1[j] then min1[j]:=smin;
          if smax<0 then smax:=0;if smin>0 then smin:=0;
        end;
      end;
    end;
    for i:=1 to n-2 do begin
      if max1[i]>max1[i+1] then max1[i+1]:=max1[i];
      if min1[i]<min1[i+1] then min1[i+1]:=min1[i];
    end;

    fillchar(b,sizeof(b),0);
    for i:=2 to n do begin
      max2[i]:=-maxlongint;min2[i]:=maxlongint;
    end;
    for i:=0 to n-2 do begin
      for j:=2 to n-i do begin
        smax:=0;smin:=0;
        for k:=1 to m do begin
          inc(b[j,k],a[j+i,k]);
          inc(smax,b[j,k]);inc(smin,b[j,k]);
          if smax>max2[j] then max2[j]:=smax;if smin<min2[j] then min2[j]:=smin;
          if smax<0 then smax:=0;if smin>0 then smin:=0;
        end;
      end;
    end;
    for i:=n downto 3 do begin
      if max2[i]>max2[i-1] then max2[i-1]:=max2[i];
      if min2[i]<min2[i-1] then min2[i-1]:=min2[i];
    end;
  end;
procedure update(x:longint);
  begin
    if x>ans then ans:=x;
  end;
begin
  repeat
    read(n,m);
    for i:=1 to n do
      for j:=1 to m do
        read(a[i,j]);
    cal(a,b,umax,umin,dmax,dmin);
    for i:=1 to n do
      for j:=1 to m do
        b[j,i]:=a[i,j];
    i:=m;m:=n;n:=i;
    cal(b,a,lmax,lmin,rmax,rmin);

    ans:=-maxlongint;
    for i:=2 to m do begin
      update(umax[i-1]*dmax[i]);
      update(umax[i-1]*dmin[i]);
      update(umin[i-1]*dmax[i]);
      update(umin[i-1]*dmin[i]);
    end;
    for i:=2 to n do begin
      update(lmax[i-1]*rmax[i]);
      update(lmax[i-1]*rmin[i]);
      update(lmin[i-1]*rmax[i]);
      update(lmin[i-1]*rmin[i]);
    end;
    writeln(ans);
  until seekeof;
end.