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

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
{$inline on}
Program HELPPM;
Const
  input  = '';
  output = '';
  maxn = 503;
  maxv = 1000000;
Var
  a: array[0..maxn,0..maxn] of integer;
  m,n,k: integer;
  area,lx,ly,rx,ry: integer;

Procedure init;inline;
Var
  f: text;
  i,j: integer;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, m, n, k);
  For i:= 1 to m do
    For j:= 1 to n do read(f, a[i,j]);

  Close(f);

  For i:= 1 to m do
    For j:= 2 to n do a[i,j]:= a[i,j] + a[i,j - 1];

  For j:= 1 to n do
    For i:= 2 to m do a[i,j]:= a[i,j] + a[i - 1,j];
End;

Procedure solve;inline;
Var
  i,j,inf,sup: integer;
Begin
  area:= maxv;
  For i:= 1 to n do
    For j:= i to n do
      If area > j - i + 1 then
        Begin
          inf:= 1;
          sup:= 1;

          Repeat
            While (a[sup,j] - a[sup,i - 1] - a[inf - 1,j] + a[inf - 1,i - 1] < k) and (sup <= m) do inc(sup);
            If sup > m then break;

            While a[sup,j] - a[sup,i - 1] - a[inf,j] + a[inf,i - 1] >= k do inc(inf);

            If area > (j - i + 1) * (sup - inf + 1) then
              Begin
                area:= (j - i + 1) * (sup - inf + 1);
                lx:= inf;
                ly:= i;
                rx:= sup;
                ry:= j;
              End;

            inc(sup);
          Until sup > m;
        End;
End;

Procedure printresult;inline;
Var
  f: text;
Begin
  Assign(f, output);
    Rewrite(f);

  If area = maxv then writeln(f, -1)
  else
    Begin
      Writeln(f, area);
      Writeln(f, lx, ' ', ly, ' ', rx, ' ', ry);
    End;

  Close(f);
End;

Begin
  init;
  solve;
  printresult;
End.

Download