THHV 2025 - DX10 - 11 - Bảng số
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 một bảng hình chữ nhật ~a~ gồm ~m~ hàng và ~n~ cột. Các hàng được đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Ô giao nhau giữa hàng ~i~ với cột ~j~ gọi là ô ~(i, j)~ có ghi một giá trị nguyên dương ~a_{ij}~.
Yêu cầu: Hãy tìm một hình chữ nhật con của bảng ~a~ thỏa mãn các điều kiện sau:
Hình chữ nhật con được chọn phải có diện tích (số hàng ~\times~ số cột) lớn nhất có thể.
Các số ghi trong hình chữ nhật được chọn phải hoàn toàn phân biệt (không có số nào xuất hiện nhiều hơn ~1~ lần).
Input
Dòng ~1~ chứa hai số nguyên dương ~m, n~ ~(m, n \le 400)~;
Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ~n~ số nguyên dương ~a_{i1}, a_{i2}, \dots, a_{in}~. Các số đều có giá trị không vượt quá ~10^6~.
Output
Một số nguyên duy nhất là diện tích hình chữ nhật con được chọn.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~30\%~ | ~m, n \le 20; a_{ij} \le 10^4~ |
| 2 | ~30\%~ | ~20 < m, n \le 100; a_{ij} \le 10^4~ |
| 3 | ~40\%~ | ~100 < m, n \le 400~ |
Sample Input 1
3 3
1 3 1
4 5 6
2 6 1
Sample Output 1
6
Bình luận