Hình vuông K×K tổng lớn nhất

Arrays Buổi 15 — Prefix Sum & Difference Array prefix-sum
Points
31
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Cho ma trận số nguyên kích thước $N \times M$ và số nguyên dương $K$ ($1 \le K \le \min(N, M)$). Hãy tìm tổng lớn nhất của một ma trận con hình vuông kích thước $K \times K$.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $N, M, K$. $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng lớn nhất tìm được.

Ví dụ
Input Output
3 4 2
1 2 -1 4
-8 -3 4 2
3 8 10 -8
19
2 2 2
-1 -2
-3 -4
-10
Giới hạn

$1 \le N, M \le 1000$, $1 \le K \le \min(N, M)$, $|A_{i,j}| \le 10^9$.

Draft saved