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

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.