1803: Добуток
Перегляд у форматі PDFДано масив \(a\) довжиною \(n\). Ціна підмасиву --- це добуток довжини підмасиву на суму двох найменших чисел.
Підмасив \(a[l..r]\) --- це частина масиву \(a\), якщо брати до уваги лише числа, що знаходяться на позиціях від \(l\) до \(r\) включно.
Наприклад, нехай дано масив \([5, 3, 1, 5, 3]\). Розглянемо підмасив \(a[2..4]\), елементи (\(a[2..4]\)) --- \([3, 1, 5]\). Його довжина --- \(3\), перший мінімум --- \(1\), другий мінімум --- \(3\). Виходить, що його ціна --- \(3 \cdot (1 + 3) = 12\). Розглянемо інший підмасив \(a[1..2]\), елементи (\(a[1..2]\)) --- \([5, 3]\). Його довжина --- \(2\), перший мінімум --- \(3\), другий мінімум --- \(5\). Виходить, що його ціна \(2 \cdot (3 + 5) = 16\).
Зверніть увагу, що якщо мінімальне число трапляється більше одного разу, то воно все одно рахується кілька разів. Наприклад, якщо є підмасив \([3, 1, 1]\), то його довжина --- \(3\), перший мінімум --- \(1\), другий мінімум --- \(1\). Тобто його ціна --- \(3 \cdot (1 + 1) = 6\).
Ваше завдання --- знайти максимальну ціну щодо всіх підмасивів довжини, як мінімум, два елементи. Тобто потрібно знайти максимальну ціну за всіма підмасивами \(a[l..r]\), де (\(1 \leq l < r \leq n\)).
Оцінювання
- (\(6\) бали): \(2 \le n \le 800\)
- (\(7\) бали): \(2 \le n \le 5\,000\)
- (\(10\) балів): \(2 \le n \le 20\,000\)
- (\(24\) балів): Усі тести згенеровано рандомно наступним чином: спершу визначається число \(n\), що відбувається не рандомно, а потім для кожного \(a_i\) (\(1 \le i \le n\) ) присвоюється значення від \(1\) до \(10^9\) включно з однаковою ймовірністю для кожного значення. \(2 \le n \le 10^5\).
- (\(17\) балів): \(2 \le a_i \le \sqrt{n}\)
- (\(36\) балів): Без додаткових обмежень
Формат вхідних даних
Перший рядок містить одне ціле число \(n\) \((2 \le n \le 10^6)\).
Другий рядок містить \(n\) цілих чисел \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le 10^9)\).
Формат вихідних даних
Виведіть одне ціле число --- відповідь на задачу.
Примітка
У першому прикладі максимум досяжний на підмасиві \(a[1..5]\), його довжина \(5\), мінімуми --- \(1\) i \(3\), добуток \((1+3) \cdot 5 = 20\).
У другому прикладі максимум досяжний на підмасиві \(a[5..6]\), його довжина \(2\), мінімуми --- \(10\) i \(77\), добуток \((10+77) \cdot 2=174\).
У третьому прикладі максимум досяжний на підмасиві \(a[2..3]\), його довжина \(2\), мінімуми --- \(2\) i \(3\), добуток \((2+3) \cdot 2=10\).
Приклад вхідних даних
5
5 3 1 5 3Приклад вихідних даних
20Приклад вхідних даних
7
1 1 3 5 10 77 5Приклад вихідних даних
174Приклад вхідних даних
3
1 2 3Приклад вихідних даних
10
Коментарі
Damn, на мові С, код зі складністю NlogN, при N <= 10^6 виконується більше 3х секунд...
Проблема малої потужності сервера, авторський розвʼязок у нас помістився у 2.5с (на офіційних змаганнях виділялося 2с) - + 1 с.