Hình chữ nhật

Xem dạng PDF

Gửi bài giải

Điểm: 100,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: HCN.INP
Output: HCN.OUT

Nguồn bài:
HNOI2122C2
Dạng bài
Ngôn ngữ cho phép
C++, Pascal, Python

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'~.

Dữ liệu nhập vào từ file văn bản HCN.INP:

  • Dòng đầu tiên gồm ba số nguyên dương ~N,M,K~ ~(N,M≤10^4; \ K≤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≤N; \ c≤M)~.

Kết quả ghi ra file văn bản HCN.OUT:

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.

Ràng buộc

  • Có ~50\%~ số test tương ứng với ~50\%~ số điểm thoả mãn: ~N,M≤50;~
  • ~30\%~ số test khác tương ứng với ~30\%~ số điểm thoả mãn: ~N,M≤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.

Ví dụ

Input
4 5 4
2 3
2 5
3 1
4 4
Output
9

Giải thích: