Cho lưới ô vuông kích thước NxN, tại ô (i,j) ghi số nguyên a[i,j].Người ta chọn một hình vuông có kích thước KxK (1 ≤ K ≤ N). Sau đó cắt hình vuông này thành từng lớp có độ dày 1 đơn vị (có dạng hình vuông rỗng ruột) có kích thước lần lượt KxK, (K-1)x(K-1)… Bạn phải chọn các lớp không liên tiếp, bắt đầu từ lớp ngoài cùng (lớp có kích thước KxK) trở vào và tổng các ô trong các lớp bạn chọn là số điểm bạn thu được.
Ví dụ, ta sẽ chọn hình vuông kích thước 4x4 như hình bên. Khi cắt hình vuông này ta chỉ được 2 lớp và tổng các ô được chọn theo cách trên là 25.
Yêu cầu: Tìm tổng điểm lớn nhất mà bạn có thể có được.
Dữ liệu: Vào từ tệp “BONUS.INP” gồm:
- Dòng 1: Ghi số nguyên dương N (N ≤ 100).
- N dòng tiếp theo, mỗi dòng ghi N số nguyên a[i,j] (|a[i,j]| ≤ 109).
Kết quả: Ghi ra tệp “BONUS.OUT”số nguyên duy nhất là kết quả tìm được.
BONUS.INP
1 -1 3 -2 1
-5 6 -3 3 -2
6 1 2 1 1
-4 -2 8 7 5
-6 0 4 -1 1
BONUS.OUT
25
Ý tưởng của em là dùng tổng tích lũy nhưng có một vấn đề là khi xét các hình vuông con bên trong e vẫn chưa có định hướng gì ạ