410753: GYM104096 E Участок на берегу

E. Участок на берегуограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Миллионер Билл подал в мэрию прекрасного курортного города заявку на покупку участка на побережье. Администрация города согласилась выделить миллионеру участок, но выставила требование: в целях соблюдения принципов городского планирования участок обязательно должен быть прямоугольной формы и одна из его сторон должна быть параллельна гряде гор, идущих вдоль побережья. Побережье представляет собой последовательность прямоугольных полос ширины один метр, одна из метровых сторон которых упирается в гряду гор, представляющую собой прямую линию. Полосы касаются друг друга боковыми сторонами. Море находится с противоположной от гор стороны полос (см. рисунок). Помогите Биллу выбрать участок максимальной площади, удовлетворяющий требованиям мэрии.

Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Входные данные

В первой строке входного файла записаны два числа: $$$n$$$ — длина берега в метрах ($$$1 \leq n \leq 10^5$$$) и $$$t$$$ — номер подзадачи. В следующей строке записаны через пробел $$$n$$$ целых неотрицательных чисел $$$h_i,\, i = 1,..,n$$$, не превосходящих $$$10^9$$$ – последовательные длины всех полос в метрах. Номер подзадачи $$$t$$$ определяет дополнительные ограничения на вид входных данных (см. описание системы оценивания ниже).

Выходные данные

В выходной файл требуется вывести единственное число — максимальную площадь участка.

Система оценки

Решение задачи оценивается независимо на каждом тесте. За каждый успешно пройденный тест, кроме тестов из условия, начисляется 2 балла. Прохождение тестов из условия является необходимым условием для оценивания задачи на остальных тестах. Остальные тесты оцениваются независимо друг от друга. Тесты разбиты на следующие группы тестов, соответствующие номеру подзадачи $$$t$$$ во входных данных задачи:

Номер подзадачи	Описание	Тесты в группе	Балл за группу
0	Тесты из условия	1 – 2	0
1	Дополнительное ограничение: $$$n \leq 1000$$$	3 – 7	10
2	Дополнительное ограничение: последовательность длин полос является монотонно неубывающей, то есть для каждого $$$i = 1, ..., n - 1$$$ выполнено: $$$h_i \leq h_{i+1}$$$	8 – 12	10
3	Дополнительное ограничение: побережье имеет форму бухты, то есть существует некоторое $$$j$$$, такое что $$$1 \leq j \leq n$$$ и $$$h_i \geq h_{i+1}$$$ для всех $$$i = 1, .., j-1$$$ и $$$h_i \leq h_{i+1}$$$ для всех $$$i = j, ..., n$$$	13 – 17	10
4	Дополнительное ограничение: побережье имеет форму мыса, то есть существует некоторое $$$j$$$, такое что $$$1 \leq j \leq n$$$ и $$$h_i \leq h_{i+1}$$$ для всех $$$i = 1, .., j-1$$$ и $$$h_i \geq h_{i+1}$$$ для всех $$$i = j, ..., n$$$	18 – 22	10
5	Дополнительное ограничение: $$$h_i \leq 100$$$ для всех $$$i = 1, ..., n$$$	23 – 27	10
6	Без дополнительных ограничений	28 – 52	50

ПримерыВходные данные

5 0
3 4 5 4 2

Выходные данные

12

Входные данные

8 0
6 7 3 4 6 8 3 5

Выходные данные

24