KHUNG HÌNH CHỮ NHẬT

 Một tấm gỗ hình chữ nhật kích thước n x m được chia thành bảng gồm n x m  ô vuông đơn vị, các dòng của bảng được đánh số từ 1 tới n từ trên xuống dưới, các cột đánh số từ 1 tới m từ trái qua phải. Ô nằm trên dòng i, cột j gọi là ô (i,j). Tấm gỗ có vân hoa, tuy nhiên không được đều lắm. Tại ô (i,j) người ta đánh giá mức độ đẹp của ô này bởi số nguyên A_ij. Giá trị ô  càng lớn thì ô đó càng đẹp. Một số ô quá xấu giá trị tương ứng của ô này có âm.

       Anh Hữu là người rất mê đồ gỗ và đang cần một khung hình chữ nhật để có thể treo các Bằng khen và Huy chương mà mình đã nhận được trong suốt quá trình học và thi đấu cờ vua. Anh Hữu cần cắt ra một tấm gỗ hình chữ nhật với các cạnh song song với tấm gỗ ban đầu và chứa trọn một số ô đồng thời độ dài mỗi cạnh không nhỏ hơn 2. Các ô nằm trên cạnh của hình chữ nhật tạo thành phần khung của tấm bảng mà anh Hữu muốn treo những thành tích của mình (nếu còn chỗ). Bởi vậy anh Hữu còn mong muốn tổng độ đẹp  của các ô nằm trên cạnh của hình chữ nhật được chọn là lớn nhất.

Yêu cầu: Cho bảng A gồm n x m số nguyên, hãy giúp anh Hữu tìm giá trị  của hình chữ nhật có tổng các ô ở biên là lớn nhất.

Dữ liệu: Vào từ file văn bản MAXFRAME.INP trong đó:

·    Dòng đầu chứa hai số n và m

·    Dòng thứ n  trong  dòng tiếp theo chứa các số a_i1, a_i2, a_i3,…,a_im .

Kết quả: Ghi vào file văn bản MAXFRAME.OUT một số nguyên duy nhất

Ví dụ:

MAXFRAME.INP	MAXFRAME.OUT
2 3 1  2 1 3 -2 1	6
4 5  2  3  1 -10  1  2  0 -1  -5 -2 -1  0  2   1 -1  2 -1 -2  -4  3	8

Giới hạn:  N, m <= 400; |a_ij| <=10⁴

test - solution - code - đề (word)

back