Thi thử TS10 Đại học Vinh 2025 - Hình chữ nhật

Xem dạng PDF

Gửi bài giải

Điểm: 35,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong 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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.