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.