Cho một bảng các ô vuông đơn vị có kích thước nxm (n, m ≤ 100; n số hàng, m số cột của bảng). Trên mỗi ô vuông đơn vị chứa các số nguyên dương.
Yêu cầu: Hãy tìm ở bảng trên hai hình chữ nhật (có thể giao nhau nhưng không trùng khít lên nhau) có kích thước pxq (p<n; q<m; p là số hàng, q là số cột của hai hình chữ nhật con) sao cho tổng của tất cả các số trên hai hình chữ nhật là lớn nhất.
Dữ liệu vào: File tên HCN.OUT
- Dòng 1 ghi bốn số n, m, p, q được ghi cách nhau bởi dấu cách.
- n dòng tiếp theo, mỗi dòng ghi m số nguyên dương và cách nhau bởi dấu cách.
Dữ liệu ra: File HCN.OUT, chứa 1 dòng ghi một số nguyên duy nhất S là diện tích lớn nhất cần tìm.
|
HCN.INP |
HCN.OUT |
|
4 7 3 3 1 2 3 1 1 3 4 5 3 1 4 0 1 2 4 6 3 4 7 1 1 9 3 8 10 0 1 0 |
84 |
Ví dụ:
|
1 |
2 |
3 |
1 |
1 |
3 |
4 |
|
5 |
3 |
1 |
4 |
0 |
1 |
2 |
|
4 |
6 |
3 |
4 |
7 |
1 |
1 |
|
9 |
3 |
8 |
10 |
0 |
1 |
0 |
var n,m,i,j,p,q,k,tam:byte;
a:array[1..100,1..100] of integer;
b:array[1..10000] of integer;
f:text;
function tong(x,y:integer):integer;
var i,j:integer;
begin
tong:=0;
for i:=x to x+p-1 do
for j:=y to y+q-1 do
tong:=tong+a[i,j];
exit(tong);
end;
begin
assign(f,'HCN.inp');reset(f);
readln(f,n,m,p,q);
for i:=1 to n do
begin
for j:=1 to m do read(f,a[i,j]);
readln(f);
end;
close(f);
assign(f,'HCN.out');rewrite(f);
k:=0;
for i:=1 to n-q+1 do
begin
for j:=1 to m-p+1 do
begin
inc(k);
b[k]:=tong(i,j);
end;
end;
for i:=1 to k-1 do
for j:=k downto i+1 do
if b[j]>b[j-1] then
begin
tam:=b[j];
b[j]:=b[j-1];
b[j-1]:=tam;
end;
writeln(f,b[1]+b[2]);
close(f);
readln;
end.
