Cắt bánh hình chữ nhật
Points
33
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Một chiếc bánh hình chữ nhật kích thước $R \times C$ ô, mỗi ô $(i, j)$ chứa lượng nho khô $a_{i,j}$. Bạn muốn cắt chiếc bánh bằng $A - 1$ nhát cắt ngang (song song với cạnh ngang, nằm giữa các hàng) để chia thành $A$ dải ngang, sau đó với mỗi dải ngang lại cắt bằng $B - 1$ nhát cắt dọc để thu được tổng cộng $A \times B$ miếng bánh hình chữ nhật.
Hãy tìm cách cắt sao cho lượng nho khô ở miếng bánh ít nho nhất là lớn nhất có thể.
Dữ liệu vào
- Dòng đầu tiên chứa bốn số nguyên $R, C, A, B$.
- $R$ dòng tiếp theo, mỗi dòng chứa $C$ số nguyên mô tả $a_{i,j}$.
Dữ liệu ra
In ra lượng nho khô lớn nhất có thể của miếng bánh ít nho nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 4 2 2 |
1 2 2 1 3 1 1 2 2 2 1 3 1 1 2 2 | 6 | | 2 3 1 2 4 1 3 2 5 1 | 6 |
Giới hạn
- $1 \le A \le R \le 500$
- $1 \le B \le C \le 500$
- $0 \le a_{i,j} \le 10^9$.
Community Discussion