Cắt bánh hình chữ nhật

Binary-search Buổi 13 — Chặt nhị phân đáp án greedy prefix-sum
Points
33
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề 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$.
Draft saved