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 |