比赛 10101115 评测结果 WWWWWWWWWW
题目名称 牛宫 最终得分 0
用户昵称 王者自由 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2010-11-15 11:18:38
显示代码纯文本
program long;
var n,m,i,j:integer;
  A,S:array[1..200,1..200]of longint;
  x,y,now,now2:array[0..200] of longint;
  w,head,tail,t,k:longint;
function Find(tmp:longint):longint;
var l,r,mid:longint;
begin
    l:=head; r:=tail;
    while l+1<r do
    begin
      mid:=(l+r) shr 1;
      if x[mid]+tmp>0 then r:=mid else l:=mid;
    end;
    if x[l]+tmp>0 then exit(y[l]) else exit(y[r]);
end;
procedure Add(tmp,k:longint);
begin
    if tmp>x[tail] then
    begin
      inc(tail);
      x[tail]:=tmp;
      y[tail]:=k;
    end;
end;
begin
  assign(input,'long.in'); reset(input);
  assign(output,'long.out'); rewrite(output);
  readln(n,m);
  w:=0; fillchar(S,sizeof(S),0);
  for i:=1 to n do
    for j:=1 to m do
      begin
        read(A[i,j]);
        S[i,j]:=S[i-1,j]+S[i,j-1]-S[i-1,j-1]+A[i,j];
      end;
  w:=1;
  for i:=1 to n do
    for j:=1 to n do
    begin
      fillchar(now,sizeof(now),0);
      for k:=1 to m do now[k]:=S[j,k]+S[i-1,k-1]-S[i-1,k]-S[j,k-1];
      fillchar(now2,sizeof(now2),0);
      for k:=1 to m do now2[k]:=now2[k-1]+now[k];
      fillchar(x,sizeof(x),0); fillchar(y,sizeof(y),0);
      head:=1; tail:=1;
      for k:=1 to m do
      begin
        if now2[k]+x[tail]<=0 then t:=k else t:=find(now2[k]);
        if w<(j-i+1)*(k-t) then w:=(j-i+1)*(k-t);
        Add(-now2[k],k);
      end;
    end;
  writeln(w);
  close(input); close(output);
end.