printРабочее место участника

printЗадачи

2093. Держать строй - 3

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В воинской части города Шатров продолжаются занятия по строевой подготовке. На этот раз Андрей Юрьевич выполняет очередное задание своего начальника Павла Андреевича. Для выполнения этого задания, Андрею Юрьевичу необходимо среди всех `n` солдат, стоящих в одной шеренге, выбрать отряд из `k` высоких солдат для выполнения строительных работ.
В качестве первого шага, Андрей Юрьевич приказал каждому солдату посчитать свой показатель роста. Для этого каждый солдат, стоящий в шеренге, должен посмотреть сначала в одну сторону и посчитать количество солдат в этой части шеренги, которые строго ниже его, потом посмотреть в другую сторону, посчитать такое же количество, и тогда сумма этих двух чисел и будет его показателем роста.
На втором шаге, основываясь на этом показателе, Андрей Юрьевич должен выбрать отряд. Поскольку за долгие дни и ночи занятий строевой подготовкой солдаты успели хорошо познакомиться и даже подружиться со своими соседями в шеренге, Андрей Юрьевич решил выбрать в шеренге такой непрерывный подотрезок из ровно `k` солдат, у которого сумма показателей роста всех солдат максимальна.
Обладая информацией о росте каждого солдата в шеренге, помогите Андрей Юрьевичу найти оптимальный подотрезок.
Первая строка входного файла содержит два целых числа: `n` и `k` (`1\ ≤\ k\ ≤\ n\ ≤\ 100000`) – количество солдат в строю и необходимый размер отряда, соответственно. Следующая строка содержит `n` целых чисел `h_i` (`1\ ≤\ h_i\ ≤\ 10^9`) – рост `i`-го слева солдата в шеренге.
В выходной файл выведите одно целое число `l` – левый конец подотрезка из `k` солдат с максимальным показателем роста. Если таких отрезков несколько, выведите самый левый.

Пример ввода 1

4 2
1 2 4 3

Пример вывода 1

3

Пример ввода 2

4 2
2 1 1 2

Пример вывода 2

1
Источник: neerc.ifmo.ru/school
loading