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.