Hình chữ nhật lớn nhất

Xem PDF




Tác giả:
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một bảng hình chữ nhật kích thước \(𝑚 \times 𝑛\) được chia thành lưới ô vuông đơn vị \(𝑚\) hàng, \(𝑛\) cột. Các hàng được
đánh số từ 1 tới \(𝑚\) theo thứ tự từ trên xuống dưới và các cột được đánh số từ 1 tới \(𝑛\) theo thứ tự từ trái qua phải.

Người ta tiến hành tô màu các ô của bảng theo từng cột: Các ô trên mỗi cột \(𝑗\) sẽ được tô từ trên xuống dưới: \(ℎ_𝑗\) ô
màu vàng tiếp đến là \(𝑚 - ℎ_𝑗\) ô màu xanh. Như vậy tình trạng màu trên bảng hoàn toàn xác định nếu ta biết được
số hàng \(𝑚\), số cột \(𝑛\) và các số nguyên \(ℎ_1, ℎ_2, … , ℎ_𝑛\).

Yêu cầu: Hãy xác định một hình chữ nhật gồm các ô trong bảng đã cho thỏa mãn các yêu cầu sau:

  • Có cạnh song song với cạnh bảng.
  • Đơn sắc (chỉ gồm các ô vàng hoặc chỉ gồm các ô xanh).
  • Diện tích lớn nhất có thể.

Input

  • Dòng 1: Chứa hai số nguyên dương \(𝑚, 𝑛 (𝑚, 𝑛 \leq 5 \times 10^5)\).
  • Dòng 2: Chứa \(𝑛\) số nguyên \(ℎ_1, ℎ_2, … , ℎ_𝑛 (\forall 𝑗: 0 \leq ℎ_𝑗 \leq 𝑚)\).

Output

  • Ghi ra một số nguyên duy nhất là diện tích hình chữ nhật tìm được.

Các số trên một dòng của Input files được ghi cách nhau ít nhất một dấu cách.

Scoring

  • Subtask \(1\) (\(9.5\%\) số điểm): \(𝑚, 𝑛 \leq 400\)
  • Subtask \(2\) (\(42.9\%\) số điểm): \(𝑚, 𝑛 \leq 10^4\)
  • Subtask \(3\) (\(47.6\%\) số điểm): \(𝑚, 𝑛 \leq 10^5\)

Example

Test 1

Input
5 9
1 3 4 4 5 4 4 3 1 
Output
21
Note

Trong test ví dụ 1, xác suất để mọi người đều có quà là \(\dfrac{7}{16}\) nên chúng ta phải in ra \(\dfrac{7}{16}\times 2^4=7\)


Bình luận


  • 0
    NguyenHuuNhatQuang 9:09 a.m. 14 Tháng 12, 2022

    DSU time =))


    • 0
      tkvinhtruongquang 6:50 p.m. 7 Tháng 9, 2021

      is this easy enough for newbie like me?


      • 1
        hungeazyITistrue 9:59 p.m. 23 Tháng 7, 2021

        Có ai gợi ý em cách ac bài này với ạ!


        • 1
          n2anndk 7:59 p.m. 27 Tháng 1, 2021

          có ai gợi ý em cách ac bài này vs ạ


          • 1
            cuom1999 6:56 a.m. 3 Tháng 8, 2020

            Đã cập nhật test (credit: mimibetty). 33AC -> 26AC.