HELPPM - Giúp ngài thủ tướng!

Tác giả: RR

Ngôn ngữ: Pascal

{$R-,Q-}
const
  FINP='';
  FOUT='';
  MAXN=501;
var
  f1,f2:text;
  kq,lu,ld,lr,ll,m,n,k:longint;
  left,down,a:array[0..MAXN,0..MAXN] of longint;
  x:array[1..MAXN] of longint;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure inp; inline;
var
  i,j:longint;
begin
  read(f1,m,n,k);
  for i:=1 to m do
  for j:=1 to n do
    read(f1,a[i,j]);
end;
procedure init; inline;
var
  i,j:longint;
begin
  for i:=1 to m do
  for j:=1 to n do
    down[i,j]:=down[i-1,j]+a[i,j];
  for i:=1 to m do
  for j:=1 to n do
    left[i,j]:=left[i,j-1]+a[i,j];
end;
var
  temp:longint;
  height,l,r,i,j,sum:longint;
procedure solve1;
begin
  kq:=maxlongint;
  for l:=1 to m do
  for r:=l to m do
  if r-l<kq then
    begin
      height:=r-l;
      for i:=1 to n do x[i]:=down[r,i]-down[l-1,i];
      j:=1; sum:=x[1];
      if (sum>=k) and (height<kq) then
        begin
          kq:=height;
          lu:=l; ld:=r; ll:=1; lr:=1;
        end;
      for i:=2 to n do
        begin
          inc(sum,x[i]);
          if sum>=k then
            begin
              while sum>=k do
                begin
                  dec(sum,x[j]);
                  inc(j);
                end;
                temp:=(height+1)*(i-j+2);
                if kq>temp then
                begin
                  kq:=temp;
                  lu:=j-1; ld:=i; ll:=l; lr:=r;
                end;
            end;
        end;
    end;
end;
procedure solve2;
begin
  kq:=maxlongint;
  for l:=1 to n do
  for r:=l to n do
  if r-l<kq then
    begin
      height:=r-l;
      for i:=1 to m do x[i]:=left[i,r]-left[i,l-1];
      j:=1; sum:=x[1];
      if (sum>=k) and (height<kq) then
        begin
          kq:=height;
          lu:=l; ld:=r; ll:=1; lr:=1;
        end;
      for i:=2 to m do
        begin
          inc(sum,x[i]);
          if sum>=k then
            begin
              while sum>=k do
                begin
                  dec(sum,x[j]);
                  inc(j);
                end;
              temp:=(height+1)*(i-j+2);
              if kq>temp then
                begin
                  kq:=temp;
                  ll:=j-1; lr:=i; lu:=l; ld:=r;
                end;
            end;
        end;
    end;
end;
procedure ans; inline;
begin
  if kq=maxlongint then begin writeln(f2,-1); exit; end;
  writeln(f2,kq);
  writeln(f2,ll,' ',lu,' ',lr,' ',ld);
end;
begin
  openF;
  inp;
  init;
  if m<n then solve1
  else solve2;
  ans;
  closeF;
end.

Download