DHBB 2023 - HVT - 10 - 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 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~, 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 mà chỉ chứa duy nhất một ký tự 'X'.
Input
Dòng ~1~: chứa ~3~ 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 tiếp theo, mỗi dòng chứa hai số nguyên dương ~d~ và ~c~ là chỉ số của 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 thỏa mãn yêu cầu của đề bài.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~50\%~ | ~1 \le N, M \le 50~ |
| 2 | ~30\%~ | ~100 \le N, M \le 500~ |
| 3 | ~20\%~ | Không có ràng buộc gì thêm |
Sample Input 1
4 5 4
2 3
2 5
3 1
4 4
Sample Output 1
9
Notes
Hình chữ nhật con gồm các ô từ hàng ~1~ đến hàng ~3~ và từ cột ~2~ đến cột ~4~ có diện tích ~9~ và chỉ chứa một ký tự 'X'.
Bình luận