PHẦN THƯỞNG (BONUS - DH 2016)

Xem dạng PDF

Gửi bài giải

Điểm: 0,10 (OI)
Giới hạn thời gian: 0.5s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
Duyen Hai 2016
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Tuấn là người thắng cuộc trong một cuộc thi "Tìm hiểu kiến thức vũ trụ" và được nhận các phần thưởng do công ty XYZ tài trợ. Các phần thưởng được bố trí trên một bảng hình chữ nhật kích thước ~m \times n~ có dạng một lưới ô vuông kích thước đơn vị. Các dòng của bảng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột của bảng được đánh số từ ~1~ đến ~n~ từ trái qua phải. Ô nằm trên giao của dòng ~i~ và cột ~j~ được gọi là ô ~(i, j)~, trên ô đó chứa một món quà có giá trị là ~a_{ij}~ ~(1 \le i \le m; 1 \le j \le n)~.

Để nhận phần thưởng, Tuấn được phép chọn một hình vuông kích thước ~k \times k~ chiếm trọn một số ô của bảng và nhận tất cả các phần quà trong các ô nằm trong hình vuông đó.

Yêu cầu: Hãy xác định tổng giá trị lớn nhất của các món quà mà Tuấn có thể nhận được.

Input
  • Dòng đầu tiên chứa ba số nguyên dương ~m, n, k~ ~(m \times n \le 10^6; k \le \min(m, n))~.
  • Dòng thứ ~i~ trong số ~m~ dòng tiếp theo chứa ~n~ số nguyên dương, số thứ ~j~ là ~a_{ij}~ ~(a_{ij} \le 1000)~.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output
  • In ra một số nguyên duy nhất là tổng giá trị lớn nhất của các món quà mà Tuấn có thể nhận được.
Sample Input
4 4 3
1 9 1 1
9 7 8 7
1 8 8 8
1 7 8 7
Sample Output
68
Notes

Chọn hình vuông từ ô ~(2, 2)~ tới ô ~(4, 4)~: ~7 + 8 + 7 + 8 + 8 + 8 + 7 + 8 + 7 = 68~.


Đang tải...