Khối k×k có tổng lớn nhất

Bối cảnh

Một ảnh nhiệt được biểu diễn bằng ma trận r × c, trong đó mỗi ô là cường độ đo tại một vị trí. Để phát hiện một vùng hoạt động mạnh, hệ thống cần chọn một khối vuông liên tiếp kích thước k×k có tổng giá trị lớn nhất. Nếu nhiều khối có cùng tổng lớn nhất, chọn khối có hàng bắt đầu nhỏ hơn; nếu vẫn bằng nhau, chọn cột bắt đầu nhỏ hơn.

Ở B11, bạn mới làm quen với ma trận hai chiều nên chưa cần dùng prefix sum 2D của các chuyên đề nâng cao. Giới hạn được thiết kế để lời giải có thể duyệt tất cả vị trí góc trái và tính trực tiếp tổng từng khối. Điểm quan trọng là quản lý bốn mức vòng lặp rõ ràng: hai vòng chọn vị trí khối và hai vòng cộng các ô bên trong.

Đây là bài Medium vì người làm phải chuyển từ xử lý từng hàng/cột sang duyệt một vùng con hình học và quản lý tie-break theo tọa độ.

Yêu cầu

1. Duyệt mọi góc trái (i,j) sao cho khối k×k còn nằm trong ma trận.
2. Với mỗi khối, dùng hai vòng lặp cộng toàn bộ k² phần tử.
3. Cập nhật tổng lớn nhất; do duyệt tọa độ tăng dần, chỉ cập nhật khi tổng lớn hơn để giữ tie sớm nhất.

Input

Dòng 1: rows cols k. Sau đó rows dòng, mỗi dòng cols số.

Output

Một dòng maxSum topRow leftCol.

Ràng buộc

1 ≤ rows, cols ≤ 100, 1 ≤ k ≤ min(rows,cols), |a[i][j]| ≤ 10^9; để bảo đảm thời gian, rows*cols*k*k ≤ 2*10^7.

Ví dụ 1

Input

4 5 2
1 2 3 4 5
5 4 3 2 1
0 0 10 10 0
1 1 10 10 1

Output

40 2 2

Giải thích

Với k=2, mỗi ứng viên là một khối 2×2. Khối có góc trái trên (2,2) chứa bốn giá trị 10,10,10,10, nên tổng bằng 40. Các khối khác chứa ít nhất một số nhỏ hơn 10 và không thể đạt tổng lớn hơn 40. Vì đây là giá trị tối đa đầu tiên khi duyệt theo hàng rồi cột, output là 40 2 2.

Ví dụ 2

Input

2 2 2
1 2
3 4

Output

10 0 0

Giải thích

Ma trận 2×2 và k=2 nên chỉ có duy nhất một khối ứng viên: toàn bộ ma trận. Tổng 1+2+3+4 = 10, góc trái trên là (0,0). Do đó kết quả là 10 0 0.

Thông tin học tập

• Module: M03
• Buổi: B11
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: 2D static arrays, submatrix enumeration, nested loops, optimization, tie-break
• Giới hạn kiến thức: B01-B11
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100