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\)
Comments
hình như note bị sai
DSU time =))
is this easy enough for newbie like me?
Có ai gợi ý em cách ac bài này với ạ!
có ai gợi ý em cách ac bài này vs ạ
Đã cập nhật test (credit: mimibetty). 33AC -> 26AC.