HSG9 Hà Nội 2022 - Hình chữ nhật
Xem dạng PDF
Gửi bài giải
Điểm:
10,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 hình chữ nhật gồm ~N~ dòng và ~M~ cột. Các dòng được đánh số từ ~1~ đến ~N~, từ trên xuống dưới. Các cột được đánh số từ ~1~ đến ~M~, từ trái sang phải. Ô ở dòng thứ ~i~ và cột thứ ~j~ được gọi là ô ~(i, j)~ và có diện tích là ~1~ đơn vị. Có một số ô đã được điền sẵn kí tự 'X'.
Yêu cầu: tìm hình chữ nhật con có diện tích lớn nhất chỉ chứa duy nhất một kí tự 'X'.
Input
- Dòng đầu tiên gồm ba số nguyên dương ~N, M, K~ (~N, M \le 10^4~; ~K \le 10^3~) mô tả kích thước của hình chữ nhật và số lượng kí tự 'X' có trong hình chữ nhật;
- ~K~ dòng sau, mỗi dòng gồm hai số nguyên dương ~d~ và ~c~ là chỉ số dòng và cột của ô điền kí tự 'X' (~d \le N~; ~c \le M~).
Output
Ghi ra diện tích của hình chữ nhật lớn nhất thoả mãn yêu cầu đề bài.
Sample Input 1
4 5 4
2 3
2 5
3 1
4 4
Sample Output 1
9
Subtasks
- Có 50% số test tương ứng với 50% số điểm thoả mãn: ~N, M \le 50~;
- 30% số test khác tương ứng với 30% số điểm thoả mãn: ~N, M \le 500~;
- 20% số test còn lại tương ứng với 20% số điểm không có ràng buộc gì thêm.
Bình luận