HSG THPT Đắk Nông 2023 - Bảng hình chữ nhật

Xem dưới dạng PDF

Gửi bài giải

Điểm: 20
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Tác giả:
Kiểu bài tập

Cho một bảng hình chữ nhật kích thước \(m \times n\) được chia làm lưới ô vuông đơn vị. Các hàng của bảng được đánh số từ \(1\) tới \(m\) và các cột được đánh số từ \(1\) tới \(n\). Ô nằm trên giao của hàng \(i\) và cột \(j\) gọi là ô \((i, j)\) và trên ô đó ghi số nguyên \(a_{ij}\).

Người ta cần tìm một hình chữ nhật có diện tích lớn nhất thỏa mãn các yêu cầu sau đây:

  • Thứ nhất: Cạnh hình chữ nhật song song với cạnh bảng và hình chữ nhật chứa trọn một số ô của bảng.
  • Thứ hai: Các số ghi trong các ô thuộc 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).

Yêu cầu

  • Em hãy lập trình tìm đáp án trên bảng đã cho.

Dữ liệu vào

  • Dòng \(1\) chứa hai số nguyên dương \(m, n \le 400\);
  • \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) số nguyên dương, số thứ \(j\) là \(a_{ij} \le 10^6\).

Dữ liệu ra

  • Một số nguyên duy nhất là diện tích hình chữ nhật được chọn theo phương án tìm được.

Ràng buộc

  • 30% điểm ứng với các test có \(n \le 20\);
  • 30% điểm ứng với các test có \(10 \le n \le 100\);
  • 40% điểm ứng với các test có \(100 \le n \le 400\).

Input 1

3 3
1 3 1   
4 5 6   
2 6 1

Output 1

6

Giải thích

  • Hình chữ nhật có diện tích lớn nhất (6 ô) thỏa mãn điều kiện nằm trong bảng, các giá trị trong ô là phân biệt và hình chữ nhật song song với cạnh bảng.

Nhận xét

Không có ý kiến tại thời điểm này.