Ô đất màu mỡ nhất

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

Một nông trại hình chữ nhật được chia thành lưới $R \times C$ ô đất. Ô ở hàng $i$, cột $j$ có độ màu mỡ là $a_{i,j}$. Người nông dân muốn chọn một khu đất hình chữ nhật liên tiếp kích thước $H \times W$ ($H$ hàng, $W$ cột) sao cho tổng độ màu mỡ của các ô trong khu đất đó là lớn nhất.

Dữ liệu vào
  • Dòng đầu tiên chứa bốn số nguyên $R, C, H, W$.
  • $R$ dòng tiếp theo, mỗi dòng chứa $C$ số nguyên mô tả ma trận $A$.
Dữ liệu ra
  • In ra một số nguyên duy nhất là tổng độ màu mỡ lớn nhất tìm được.
Ví dụ
Dữ liệu vào Dữ liệu ra
3 4 2 2
1 2 -1 4
-3 5 2 1
0 3 -2 4
8
Giới hạn
  • $1 \le H \le R \le 1000$
  • $1 \le W \le C \le 1000$
  • $-10^6 \le a_{i,j} \le 10^6$
Draft saved