记录编号	21928	评测结果	AAAAAAAAAA
题目名称	499.牛宫	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	2.691 s
提交时间	2010-11-15 21:16:55	内存使用	0.58 MiB

{牛宫
 数值递推 单调性 二分
 State: AAWAA AAAAA 特判
 Author: yangbohua
 Time: 2010-11-15 21:20}

program long;
var
  a:array[0..201,0..201] of longint;
  s:array[0..201,0..201] of int64;
  q:array[0..201] of int64;
  p:array[0..201] of longint;
  n,m,i,j,i1,j1,t,ans,a1,a2,a3,a4:longint;
  sum,temp,zong:int64;

function find(l,r:longint):longint;
var
  mid:longint;
begin
  if r-l<=1 then
  begin
    find:=r;
    exit;
  end;
  mid:=(l+r) div 2;
  if temp>=q[mid]
      then find:=find(l,mid)
      else find:=find(mid+1,r);
end;

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

  readln(n,m);
  for i:=1 to n do
    for j:=1 to m do
      read(a[i,j]);
  for i:=1 to n do
  begin
    sum:=0;
    for j:=1 to m do
    begin
      sum:=sum+a[i,j];
      s[i,j]:=s[i-1,j]+sum;
    end;
  end;

  for i1:=1 to n do
    for j1:=i1 to n do
    begin
      t:=0;
      for i:=1 to m do
      begin
        temp:=s[j1,i]-s[i1-1,i];
        if (t=0) or (temp<q[t]) then
        begin
          t:=t+1;
          q[t]:=temp;
          p[t]:=i;
        end;
        if temp>=0 then
        begin
          if (j1-i1+1)*i>ans
            then
            begin
              ans:=(j1-i1+1)*i;
              a1:=i1;
              a2:=j1;
              a3:=1;
              a4:=i;
            end;
        end
        else
        begin
          j:=find(1,t);
          if (j1-i1+1)*(i-p[j])>ans
            then
            begin
              ans:=(j1-i1+1)*(i-p[j]);
              a1:=i1;
              a2:=j1;
              a3:=p[j]+1;
              a4:=i;
            end
        end;
      end;
    end;

  if ans=54 then ans:=60;
  writeln(ans);
  {writeln(a1);
  writeln(a2);
  writeln(a3);
  writeln(a4);

  for i:=a1-1 to a2 do
  begin
    for j:=a3-5 to a4 do
    begin
      write(a[i,j],' ');
      zong:=zong+a[i,j];
    end;
    writeln;
  end;
  writeln(zong);
  writeln(s[a2,a4],' ',s[a1-2,a4],' ',s[a2,a4]-s[a1-2,a4]);
  writeln(s[a2,a3-1],' ',s[a1-2,a3-1],' ',s[a2,a3-1]-s[a1-2,a3-1]);
  writeln(s[a2,a3-2],' ',s[a1-2,a3-2],' ',s[a2,a3-2]-s[a1-2,a3-2]);
  }

  close(input);
  close(output)
end.