Trại hè Hùng Vương 2025 - 11 - Bảng số
Xem dạng PDF
Gửi bài giải
Điểm:
35,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 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:
- 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 một lần);
- 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ể.
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
Ghi ra một số nguyên duy nhất là diện tích hình chữ nhật con được chọn.
Sample Input
3 3
1 3 1
4 5 6
2 6 1
Sample Output
6
Giải thích
Hình chữ nhật gồm các số được tô đậm trong input. Hình chữ nhật có góc trái trên là ô ~(1, 1)~ và góc phải dưới là ô ~(3, 2)~.
1 3
4 5
2 6
Ràng buộc
- Subtask 1 (30% số điểm): ~m, n \le 20; a_{ij} \le 10^4~;
- Subtask 2 (30% số điểm): ~20 < m, n \le 100; a_{ij} \le 10^4~;
- Subtask 3 (40% số điểm): ~100 < m, n \le 400~.
Bình luận