Thi thử TS10 Đại học Vinh 2025 - Hình chữ nhật
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho một bảng ~m \times n~ gồm ~m~ hàng được đánh số từ ~1 \rightarrow m~ từ trên xuống dưới và ~n~ cột được đánh số từ ~1 \rightarrow n~ từ trái qua phải. Ô ~(i, j)~ là ô ở hàng thứ ~i~ và cột thứ ~j~ chỉ chứa số 0 hoặc số 1. Một bảng con của bảng là một hình chữ nhật có các cạnh song song với các cạnh của bảng số.
Yêu cầu: Hãy tìm bảng con có diện tích lớn nhất gồm toàn số 1 của bảng số đã cho.
Input
Dòng đầu tiên ghi hai số nguyên dương ~m, n~ ~(m, n \le 1000)~; ~m~ dòng tiếp theo, mỗi dòng gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ với ~a_i \in \{0, 1\}~ ~(i = 1 \rightarrow n)~.
Output
Ghi ra một dòng duy nhất là diện tích lớn nhất của bảng con các số 1.
Sample Input 1
3 5
0 0 1 1 0
0 1 1 1 0
0 0 1 1 1
Sample Output 1
6
Giải thích
Bảng con thỏa mãn yêu cầu bài toán là bảng có đỉnh trái trên ~(1, 3)~ và đỉnh phải dưới ~(3, 4)~. Diện tích của bảng con này là ~3 \times 2 = 6~.
Subtasks
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~0 < m, n \le 20~ |
| 2 | ~30\%~ | ~20 < m, n \le 100~ |
| 3 | ~50\%~ | ~100 < m, n \le 1000~ |
Bình luận