#251. CHOOSE1 - Chọn hình Ver 1

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Chưa có dữ liệu
Đưa lên bởi: Chùm CUỐI

Đề bài

Cho lưới ô vuông kích thước m dòng và n cột, các dòng được đánh số từ 1 tới m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái sang phải. Ở mỗi ô (i, j) có ghi một số nguyên a_{ij}\ (2 ≤ m, n ≤ 500, |a_{ij}| ≤ 10^7) . Phải lựa chọn 4 ô, sao cho tâm của 4 ô này sẽ là đỉnh của một hình chữ nhật có cạnh song song với cạnh của lưới và tổng các số trong 4 ô đó là lớn nhất.

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên m, n ;
  • m dòng sau, mỗi dòng chứa n số nguyên mô tả một dòng của lưới.

Dữ liệu ra:

  • Chứa số nguyên r là tổng lớn nhất tìm được.

Ví dụ:

Dữ liệu vào:
5 5
1 1 1 1 1
1 2 1 1 1
1 1 1 1 1
1 1 1 3 1
1 1 1 1 1
Dữ liệu ra:
7
Dữ liệu vào:
5 5
1 -1 -1 -1 -1
-1 -2 -1 -1 -1
-1 -1 -1 -1 -1
-1 -1 -1 -3 -1
-1 -1 -1  1 -1
Dữ liệu ra:
0