Ba hình vuông

Điểm: 0,01 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

bedao

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho bảng hai chiều kích thước ~n\times m~, với ô ~(i,j)~ có giá trị là ~a_{i,j}~. Nhiệm vụ của bạn là chọn ra ba hình vuông kích thước ~k\times k~ không giao nhau sao cho tổng giá trị của các ô thuộc ít nhất một hình vuông là lớn nhất.

Input

Dòng đầu tiên gồm ba số nguyên dương ~n,m,k~ tương ứng với kích thước của bảng và kích thước của mỗi hình vuông ~(1\le n,m\le 1500, 1\le k\le min(n,m))~. Dữ liệu đảm bảo có thể chọn ra ba hình vuông kích thước ~k\times k~ không giao nhau trên bảng.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo gồm ~m~ số nguyên ~a_{i,1},a_{i,2},\dots,a_{i,m}~ tương ứng với giá trị của các ô trên bảng ~(0\le a_{i,j}\le 500)~.

Output

In ra duy nhất một số nguyên là tổng giá trị tối đa có thể đạt được.

Sample Input 1

9 9 3
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9

Sample Output 1

Notes

Phương án tối ưu cho test ví dụ được mô tả ở hình phía dưới (các ô màu xanh lá tương ứng với các ô được bao phủ bởi ít nhất một hình vuông).

Bình luận

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

vuongbankien012 đã bình luận lúc 9, Tháng 2, 2026, 10:57

hint:

nhận xét rằng chúng ta có 2 TH chính để có đc 3 hình vuông lớn nhất, TH1 là ở 1 điểm chúng ta sẽ có 1 ô vuông từ điểm 1,1 ts điểm đó,1 ô vuông nữa sẽ nằm trong ô vuông từ điểm đó đến ô 1,m và 1 ô vuông nữa sẽ là nằm trong các hàng dưới điểm đó, TH2 là 3 ô vuông sẽ nằm cách biệt nhau và được phân chia bởi 2 hàng, vd t chia 2 hàng x và y thì 1 ô sẽ nằm từ hàng 1 ts x, 1 ô từ hàng x ts y bà 1 ô từ hàng y ts n,các TH còn lại ta chỉ việc xoay bảng 3 lần nữa thì sẽ có tất cả TH trong đây, để xử lí TH1 thì ta sẽ dùng 2 dp[i][j] vs ý nghĩa là ô vuông k*k lớn nhất từ điểm 1,1 ts điểm i,j và từ điểm 1,m ts điểm i,j, và hàm max khác dùng trong cả 2 TH là ô vuông có đáy năm trên hàng i, ở TH 2 thì ta duyệt 2 for và dùng biến max và mảng sufmax ý nghĩa là max của ô kxk từ hàng n ts hàng i: code tham khảo https://ideone.com/0jK72A