Question

[0o0 Nhok kawaii 0o0]

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

Answer 1

[Giao Huỳnh]

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.