Задача A1. Чемпионат по устному счету

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Председатель жюри чемпионата по устному счету придумал новое задание для участников чемпионата. Исходно на доске выписывается n целых чисел: a1, a2, …, an. После этого участник должен выполнять команды двух типов:

  1. Стереть i-е число с доски и записать вместо него число x. То есть, если на доске были записаны числа a1, a2, …, an,~ то после выполнения команды числа будут равны: a1, …, ai − 1, x, ai + 1, …, an.

  2. Циклически сдвинуть последовательность чисел на k вправо. То есть, если на доске были записаны числа a1, a2, …, an, то после выполнения команды числа будут равны: an − k + 1, an − k + 2, …, an, a1, a2, …, an − k.

После выполнения каждой команды участник должен вычислить сумму всех чисел, записанных на доске, и сообщить ее жюри. Чтобы подготовиться проверять ответы участников, членам жюри необходимо самим вычислить требуемые суммы.

Формат входных данных

В первой строке записано целое число n — количество чисел, изначально записанных на доске (2 ≤ n ≤ 105).

Во второй строке через пробел записаны n целых чисел: a1, a2, …, an — числа, изначально выписанные на доске ( − 109 ≤ ai ≤ 109).

В третьей строке записано целое число q — количество команд, которые необходимо выполнить (1 ≤ q ≤ 105).

В каждой из следующих q строк записана очередная команда в следующем формате:

Формат выходных данных

В качестве ответа выведите q строк, в каждой из которых записано одно целое число.

В i-й строке должна быть записана сумма чисел на доске после выполнения первых i команд.

Обратите внимание, что ответ может быть достаточно большим и для его хранения потребуется 64-битный тип данных, int64 в паскале, long long в C++, long в Java.

Ограничения

2 ≤ n ≤ 105

 − 109 ≤ ai ≤ 109

1 ≤ q ≤ 105

1 ≤ i ≤ n;  − 109 ≤ x ≤ 109

1 ≤ k < n

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
1 22 2 ≤ n ≤ 1 000, есть только команды первого типа полная
2 17 2 ≤ n ≤ 1 000, во всех командах второго типа k = 1 полная
3 23 2 ≤ n ≤ 1 000 1, 2 полная
4 38 1 — 3 первая ошибка

Замечание

Рассмотрим пример из условия. Изначально последовательность записанных на доске чисел равна: 4,~1,~2,~1,~5,~3.

После первой команды последовательность циклически сдвигается на 3 элемента вправо. Новая последовательность: 1,~5,~3,~4,~1,~2. Сумма чисел равна: 1 + 5 + 3 + 4 + 1 + 2 = 16.

После второй команды необходимо заменить третий элемент последовательности на число 10. Новая последовательность: 1,~5,~10,~4,~1,~2. Сумма чисел равна: 1 + 5 + 10 + 4 + 1 + 2 = 23.

После третьей команды заменить четвертый элемент на число 4. Так как четвертый элемент уже равен 4, последовательность не изменяется. Сумма чисел также равна 23.

После четвертой команды последовательность циклически сдвигается на 1: 2,~1,~5,~10,~4,~1. Сумма чисел не изменилась.

Наконец, после пятой команды последовательность становится равна:  − 10,~1,~5,~10,~4,~1. Сумма чисел в итоговой последовательности равна  − 10 + 1 + 5 + 10 + 4 + 1 = 11.

Примеры тестов

Стандартный вход Стандартный выход
1
6
4 1 2 1 5 3
5
2 3
1 3 10
1 4 4
2 1
1 1 -10
16
23
23
23
11
2
3
1000000000 1000000000 1000000000
3
1 2 999999999
2 2
1 2 999999999
2999999999
2999999999
2999999998

Задача A2. Прыгающий робот

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Компания «Flatland Dynamics» разрабатывает прыгающего робота. Для испытания робота используется полигон, на котором организован круговой маршрут из n специальных платформ, пронумерованных от 1 до n. Расстояние между i-й и i + 1-й платформой равно di, аналогично расстояние между n-й и 1-й платформой равно dn.

Робот оснащен искусственным интеллектом и в процессе испытания учится прыгать все дальше. В любой момент времени робот характеризуется своей ловкостью — целым числом a. Робот может перепрыгнуть с платформы i на платформу i + 1, если a ≥ di. Аналогично, прыжок с n-й платформы на 1-ю возможен, если a ≥ dn. При этом после каждого прыжка ловкость робота увеличивается на~1.

Разработчики робота выбирают одну из платформ в качестве стартовой. Они считают эксперимент удачным, если робот может, совершив n прыжков от текущей платформы к следующей, завершить полный круг и вернуться на ту же платформу. Разработчикам необходимо выяснить, для какого минимального значения начальной ловкости робота им удастся провести эксперимент и с какой платформы роботу следует начать прыжки.

Формат входных данных

На первой строке ввода находится число n (3 ≤ n ≤ 107).

Вторая строка содержит одно целое число f, которое описывает формат, в котором задан массив расстояний между платформами.

Если f = 1, то на третьей строке находятся n целых чисел d1, d2, …, dn (1 ≤ di ≤ 109).

Если f = 2, то на третьей строке находится число m (2 ≤ m ≤ min(n, 105)) и три целых числа x, y и z (0 ≤ x, y, z ≤ 109). На четвертой строке находятся m целых чисел c1, c2, …, cm (1 ≤ ci ≤ 109). Значения di вычисляются по следующим формулам.

Если 1 ≤ i ≤ m, то di = ci.

Если m + 1 ≤ i ≤ n, то di = ((x⋅ di − 2 + y⋅ di − 1 + z)mod 109) + 1.

Здесь mod означает остаток от целочисленного деления, в языках C++, Java и Python он обозначается символом «%».

Формат выходных данных

Требуется вывести два целых числа: минимальную допустимую начальную ловкость a и номер стартовой платформы, на которую можно разместить робота, чтобы успешно провести эксперимент.

Если возможных стартовых платформ для минимальной начальной ловкости несколько, можно вывести любую из них.

Ограничения

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
115n ≤ 300, f = 1, di ≤ 300первая ошибка
217n ≤ 5000, f = 11первая ошибка
310 n ≤ 100 000, f = 1, гарантируется, что оптимально начать с первой платформыпервая ошибка
420n ≤ 100 000, f = 11 — 3первая ошибка
55f = 2, гарантируется, что оптимально начать с первой платформы3первая ошибка
633f = 21 — 5первая ошибка

Пояснение к примеру

Во втором примере массив расстояний между платформами равен [1, 2, 3, 4, 5, 18, 45, 112, 273, 662]. Значения от d6 до d10 вычисляются по формулам:

d6 = ((1⋅ d4 + 2⋅ d5 + 3mod 109) + 1 = ((1⋅ 4 + 2⋅ 5 + 3)mod 109) + 1 = 18

d7 = ((1⋅ d5 + 2⋅ d6 + 3mod 109) + 1 = ((1⋅ 5 + 2⋅ 18 + 3)mod 109) + 1 = 45

d8 = ((1⋅ d6 + 2⋅ d7 + 3mod 109) + 1 = ((1⋅ 18 + 2⋅ 45 + 3)mod 109) + 1 = 112

d9 = ((1⋅ d7 + 2⋅ d8 + 3mod 109) + 1 = ((1⋅ 45 + 2⋅ 112 + 3)mod 109) + 1 = 273

d10 = ((1⋅ d8 + 2⋅ d9 + 3mod 109) + 1 = ((1⋅ 112 + 2⋅ 273 + 3)mod 109) + 1 = 662

Примеры тестов

Стандартный вход Стандартный выход
1
5
1
3 7 4 2 5
4 3
2
10
2
5 1 2 3
1 2 3 4 5
653 1

Задача A3. Треугольная головоломка

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Головоломка состоит из n треугольников. Чтобы решить головоломку, необходимо выбрать из них четыре треугольника и собрать из них большой треугольник по следующей схеме:

Треугольники не должны пересекаться, в объединении они должны давать треугольник. Ровно по одному из выбранных треугольников должны находиться в углах, а один треугольник должен располагаться в центре.

Треугольники лежат на столе, их можно свободно вращать и двигать, но нельзя зеркально отражать.

Формат входных данных

В первой строке дано одно целое число t — номер теста.

В второй строке дано одно целое число n — количество треугольников в головоломке (4 ≤ n ≤ 30).

В следующих n строках дано описание треугольников. Один треугольник описывается координатами трех своих углов, данных в порядке обхода треугольника против часовой стрелки. Все координаты по модулю не превышают 105. Гарантируется, что треугольники не являются вырожденными. В исходном расположении треугольники могут пересекаться.

Формат выходных данных

В первой строке выведите одно целое число — количество наборов из четырех треугольников, из которых можно собрать большой треугольник по указанной схеме.

В следующих строках выведите наборы. Каждый набор задается номерами треугольников, которые в него входят. Треугольники внутри набора можно выводить в любом порядке. Наборы можно выводить в любом порядке.

Ограничения

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

В этой задаче потестовая оценка. Каждый тест оценивается независимо и стоит 5 баллов.

Тесты удовлетворяют следующим ограничениям:

Тест Описание теста
1тест из примера, не оценивается
2тест из примера, не оценивается
3Все треугольники равны с точностью до поворота, n ≤ 30
4У каждого треугольника есть горизонтальная и вертикальная стороны, все треугольники равнобедренные, n ≤ 10
5У каждого треугольника есть горизонтальная и вертикальная стороны, все треугольники равнобедренные, n ≤ 30
6У каждого треугольника есть горизонтальная и вертикальная стороны, n ≤ 10
7У каждого треугольника есть горизонтальная и вертикальная стороны, n ≤ 30
8Все треугольники прямоугольные, n ≤ 10
9Все треугольники прямоугольные, n ≤ 30
10Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, n ≤ 10
11Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, n ≤ 20
12Для каждой четверки треугольников, из которой можно собрать треугольник, гарантируется, что треугольник можно собрать не вращая треугольники, n ≤ 30
13n = 10
14n = 10
15n = 10
16n = 20
17n = 20
18n = 20
19n = 30
20n = 30
21n = 30
22n = 30

Пояснение к примеру

В первом примере из данных четырех треугольников можно собрать один. При этом треугольники не требуется вращать.

Во втором примере все треугольники имеют одинаковую форму прямоугольного треугольника с длинами катетов равными 1. Из любых четырех треугольников можно собрать один.

Примеры тестов

Стандартный вход Стандартный выход
1
1
4
0 0 6 2 1 2
0 0 5 0 6 3
0 0 3 1 1 3
0 0 6 3 3 6
1
1 2 3 4 
2
2
6
0 0 1 0 1 1
0 1 0 0 1 0
-1 0 0 0 0 1
1 1 0 1 1 0
-1 0 0 -1 0 0
0 0 1 1 0 1
15
1 2 3 4 
1 2 3 5 
1 2 3 6 
1 2 4 5 
1 2 4 6 
1 2 5 6 
1 3 4 5 
1 3 4 6 
1 3 5 6 
1 4 5 6 
2 3 4 5 
2 3 4 6 
2 3 5 6 
2 4 5 6 
3 4 5 6 

Задача A4. Массивы-палиндромы

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Кай работает в лаборатории изучения массивов, он экспериментирует с двумя массивами натуральных чисел: A = [a1, a2, …, an] длины n и B = [b1, b2, …, bm] длины m.

Эксперимент, который проводит Кай, устроен следующим образом. У каждого из массивов отбрасывается произвольный, возможно пустой, префикс, а также произвольный, возможно пустой, суффикс, таким образом, чтобы оставшиеся части массивов имели равную длину. Обозначим получившиеся массивы как A и B, а их длину как k. Затем Кай суммирует поэлементно получившиеся массивы, итоговый массив Кай обозначает как C = [c1, c2, …, ck].

Пусть, например, n = 5, A = [4, 3, 3, 2, 1], m = 6, B = [4, 1, 5, 1, 3, 2], от массива A отбрасывается первый и последний элемент, от массива B три первых. После этого массивы имеют вид A′ = [3, 3, 2], B′ = [1, 3, 2], результат их поэлементного суммирования C = [4, 6, 4].

Задача Кая заключается в том, чтобы получать такие C, которые являются массивами-палиндромами, то есть если числа на первой и последней позиции совпадают, числа на второй и предпоследней позиции совпадают, и так далее, для всех i числа на позициях i и k − i + 1 совпадают.

Помогите Каю понять, какой максимальный по длине массив-палиндром он может получить в результате эксперимента.

Формат входных данных

В первой строке ввода даны два целых числа n и m — количество элементов в первом и во втором массиве, соответственно (1 ⩽ n, m ⩽ 100 000).

Во второй строке ввода даны n целых чисел ai — массив A (1 ⩽ ai ⩽ 100).

В третьей строке ввода даны m целых чисел bj — массив B (1 ⩽ bj ⩽ 100).

Формат выходных данных

Выведите единственное целое число — максимальное k, что Кай в результате эксперимента может получить массив-палиндром длины k.

Ограничения

1 ⩽ n, m ⩽ 100 000

1 ⩽ ai ⩽ 100

1 ⩽ bj ⩽ 100

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
1 13 n, m ≤ 300 первая ошибка
2 33 все элементы массива B одинаковые первая ошибка
3 16 n ≤ 500, m ≤ 105 1 первая ошибка
4 38 1 — 3 первая ошибка

Примеры тестов

Стандартный вход Стандартный выход
1
5 6
4 3 3 2 1
4 1 5 1 3 2
3

Задача B1. Новый год в детском саду

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

В детском саду готовятся к новому году, и воспитательница решила организовать детей, чтобы они подготовили украшения и отправили их Санте Клаусу для украшения своих оленей.

Дети с интересом восприняли идею и вырезали из бумаги a звездочек и b снежинок. Теперь они планируют отправить их Санте Клаусу по почте. Им так понравились вырезанные ими украшения, что они, возможно, решат оставить себе часть. Таким образом, дети могут отправить Санте x звездочек и y снежинок, где 0 ≤ x ≤ a и 0 ≤ y ≤ b. Чтобы Санта не расстроился, дети должны отправить ему хотя бы одно украшение. То есть должно выполняться также условие x + y > 0.

Чтобы все олени выглядели красиво, на каждом должно оказаться одинаковое количество украшений. Известно, что у Санты n оленей, поэтому если будут отправлены x звездочек и y снежинок, величина x + y должна делиться на n.

Воспитательница заинтересовалась: а сколько есть всего различных способов составить посылку Санте Клаусу. Два способа считаются различными, если в них отличается количество звездочек или количество снежинок.

Формат входных данных

В одном наборе входных данных содержатся несколько тестов. Каждый тест следует решить независимо.

Первая строка входных данных содержит целое число t — количество тестов (1 ≤ t ≤ 105).

Следующие строки описывают тесты, по одному на строке. Описание теста состоит из трех целых чисел n, a и b — количество оленей у Санты, количество звездочек и количество снежинок, вырезанных детьми (4 ≤ n ≤ 109; 0 ≤ a, b ≤ 109).

Формат выходных данных

Выведите t чисел. Для каждого теста выведите одно число: количество способов составить посылку для Санты Клауса.

Ограничения

1 ≤ t ≤ 105

4 ≤ n ≤ 109; 0 ≤ a, b ≤ 109

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
1 10 t = 1, a, b ≤ 1000 первая ошибка
2 10 t ≤ 1000, a = 0 первая ошибка
3 15 t ≤ 1000, a, b < n ≤ 1000 первая ошибка
4 10 t ≤ 1000, a, b ≤ 1000 1, 3 первая ошибка
5 15 t = 1, n ≤ 1000 первая ошибка
6 10 t ≤ 1000, n ≤ 1000 3, 5 первая ошибка
7 30 нет 1 — 6 первая ошибка

Замечание

В первом тесте у Санты 4 оленя, а дети вырезали 2 звездочки и 2 снежинки. Здесь подходит только один набор — нужно отправить все вырезанные украшения.

Во втором тесте у Санты также 4 оленя, но дети вырезали 4 звездочки и 4 снежинки. Здесь подходит 6 наборов: 0 звездочек и 4 снежинки, 1 звездочка и 3 снежинки, 2 звездочки и 2 снежинки, 3 звездочки и 1 снежинка, 4 звездочки и 0 снежинок, а также 4 звездочки и 4 снежинки.

Примеры тестов

Стандартный вход Стандартный выход
1
4
4 2 2
4 4 4
6 5 5
8 13 17
1
6
5
30

Задача B2. Сортировка дробей

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

На доске выписано две последовательности из n различных целых чисел: A = [a1, a2, …, an] и B = [b1, b2, …, bn].

Составим из них n2 дробей вида ai / bj, сократим каждую дробь и отсортируем их по неубыванию.

Задано число q и q целых чисел c1, c2, …, cq. Для каждого j следует выдать cj-ю в неубывающем порядке дробь из получившихся.

Формат входных данных

На первой строке ввода находятся числа n и q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105, q ≤ n2).

Дополнительно выполняется неравенство n⋅ q ≤ 105.

На второй строке ввода находятся n различных целых чисел a1, a2, …, an (1 ≤ ai ≤ 106).

На третьей строке ввода находятся n различных целых чисел b1, b2, …, bn (1 ≤ bi ≤ 106).

На четвертой строке ввода находятся q различных целых чисел c1, c2, …, cq (1 ≤ ci ≤ n2).

Формат выходных данных

Выведите q строк. На j-й строке выведите cj-ю по неубыванию дробь среди получившихся. Дробь p / q следует выводить в формате {p q}, дробь должна быть несократимой.

Ограничения

1 ≤ n ≤ 105, 1 ≤ q ≤ 105, q ≤ n2

n⋅ q ≤ 105

1 ≤ ai ≤ 106

1 ≤ bi ≤ 106

1 ≤ ci ≤ n2

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
114n ≤ 50первая ошибка
213n ≤ 5001первая ошибка
315q ≤ 100, ci ≤ 100первая ошибка
421ci ≤ 1053первая ошибка
5371 − 4первая ошибка

Пояснение к примеру

В примере дроби исходно равны:

[32, 33, 34, 35, 42, 43, 44, 45, 12, 13, 14, 15, 22, 23, 24, 25],

после сокращения

[32, 11, 34, 35, 21, 43, 11, 45, 12, 13, 14, 15, 11, 23, 12, 25],

после сортировки

[15, 14, 13, 25, 12, 12, 35, 23, 34, 45, 11, 11, 11, 43, 32, 21].

Примеры тестов

Стандартный вход Стандартный выход
1
4 8
3 4 1 2
2 3 4 5
1 16 2 4 5 6 10 15
1 5
2 1
1 4
2 5
1 2
1 2
4 5
3 2

Задача B3. Оптические каналы связи

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Всего во Флатландии n городов, пронумерованных от 1 до n, столица Флатландии имеет номер 1. Компьютерная сеть Флатландии устроена следующим образом: в каждом городе есть один центр подключения, который может быть связан с некоторыми другими центрами с помощью проводных каналов связи. При этом между любыми двумя городами есть ровно один маршрут по каналам связи, иначе говоря, сеть представляет собой дерево. Для города i, где i > 1, обозначим первый город на маршруте от города i до столицы как pi.

Запланирована модернизация сети Флатландии, в результате которой некоторые каналы связи будут заменены на более современные оптические. Оптические каналы могут быть проложены только вместо существующих проводных. Стоимость замены канала, который соединяет город i с городом pi, равна wi. Из-за ограничений технологии любой центр подключения может быть непосредственно подключен оптическими каналами не более чем к k другим центрам.

Министерство связи Флатландии хочет составить такой план модернизации каналов, чтобы после его выполнения связность сети по оптическим каналам связи была как можно выше. Поэтому необходимо выбрать для модернизации как можно больше каналов. Но при этом стоимость модернизации желательно минимизировать, поэтому при равном количестве необходимо выбрать для модернизации каналы с минимальной суммарной стоимостью.

Помогите специалистам министерства выбрать каналы для модернизации.

Формат входных данных

На первой строке ввода находятся два целых числа n и k (2 ≤ n ≤ 105, 1 ≤ k ≤ 100).

На следующих n − 1 строках заданы описания каналов, (i − 1)-я из этих строк содержит два целых числа: pi и wi (1 ≤ pi ≤ i, 0 ≤ wi ≤ 109).

Формат выходных данных

Выведите два целых числа cnt и cost: максимальное число каналов, которое удастся модернизировать и минимальную стоимость, за которую можно модернизировать такое число каналов.

Ограничения

2 ≤ n ≤ 105, 1 ≤ k ≤ 100

1 ≤ pi ≤ i, 0 ≤ wi ≤ 109

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
15n ≤ 15, k = 1, wi = 0первая ошибка
25n ≤ 15, wi = 01первая ошибка
33n ≤ 151, 2первая ошибка
47k = 1, wi = 01первая ошибка
55k = 11, 4первая ошибка
67k ≤ 2, wi = 01, 4первая ошибка
74k ≤ 21, 4, 5, 6первая ошибка
811n ≤ 100, wi = 01, 2первая ошибка
94n ≤ 1001, 2, 3, 8первая ошибка
1011n ≤ 2 000, wi = 01, 2, 8первая ошибка
114n ≤ 2 0001, 2, 3, 8, 9, 10 первая ошибка
1220wi = 01, 2, 4, 6, 8, 10первая ошибка
13141 — 12первая ошибка

Пояснение к примеру

Конфигурация сети в первом примере до и после модернизации показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно 4. Стоимость модернизации любого канала равна 0 и не показана.

Есть и другие подходящие решения, в которых модернизируется 4 канала.

Конфигурация сети во втором примере до и после модернизациии показана на рисунке ниже. Каналы, которые необходимо модернизировать, показаны жирными линиями. Максимальное число каналов, которое можно модернизировать, равно 6. Стоимость модернизации канала показана рядом с каналом, суммарная стоимость модернизации каналов в оптимальном решении равна 27.

Примеры тестов

Стандартный вход Стандартный выход
1
8 2
1 0
1 0
1 0
2 0
2 0
2 0
1 0
4 0
2
8 3
1 5
1 2
1 4
2 6
2 7
2 2
1 6
6 27

Задача B4. Подарки

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Дед Мороз предлагает Вове выбрать подарки на Новый год.

Перед мальчиком лежат n подарков в ряд. Каждый подарок характеризуется целым числом, у i-го подарка оно равно ai — количество удовольствия, которое подарок принесёт Вове. Удовольствие может быть как положительным, так и отрицательным, а также равным нулю.

Дед Мороз предложил Вове выбрать два числа l и r таких, что 1 ≤ l ≤ r ≤ n, и взять все подарки с номерами от l до r. Однако k подарков с максимальными характеристиками среди выбранных Вова должен отдать своей младшей сестре Маше. Остальные подарки Вова забирает себе.

Вова хочет выбрать числа l и r так, чтобы суммарное удовольствие от подарков, доставшихся именно ему, было максимальным. Общее удовольствие от набора подарков — это сумма значений ai для подарков в наборе.

Помогите Вове выбрать числа l и r так, что 1 ≤ l ≤ r ≤ n, r − l + 1 ≥ k и общее удовольствие от выбранных подарков без учёта подарков, доставшихся Маше, максимально.

Формат входных данных

В первой строке записаны два целых числа n и k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ min(100, n)) — количество подарков перед Вовой и количество подарков, которые требуется отдать Маше.

Во второй строке заданы n целых чисел через пробел a1, a2, …, an ( − 109 ≤ ai ≤ 109) — количество удовольствия, приносимого подарками.

Формат выходных данных

Выведите единственное число — общее удовольствие от выбранных Вовой подарков без учёта тех, что достались Маше.

Ограничения

1 ≤ n ≤ 200 000, 0 ≤ k ≤ min(100, n)

 − 109 ≤ ai ≤ 109

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
1 7 n ≤ 200 первая ошибка
2 8 n ≤ 1000 1 первая ошибка
3 10 n ≤ 6000 1, 2 первая ошибка
4 8 k = 0 первая ошибка
5 14 k = 1 первая ошибка
6 39 n ≤ 80 000 1 — 3 первая ошибка
7 14 1 — 6 первая ошибка

Замечание

В первом примере Вова ничего не должен отдавать Маше, поэтому он выберет l = 3, r = 5, и общее удовольствие от выбранных подарков будет равняться 5 + ( − 1) + 7 = 11.

Во втором примере Вова должен будет отдать Маше подарок с самым большим количеством удовольствия. Тогда он так же выберет l = 3, r = 5, однако общее удовольствие будет равняться 5 + ( − 1) = 4.

В третьем примере Вова должен отдать два подарка с наибольшими характеристиками. В таком случае одним из оптимальных вариантов будет выбрать l = 1, r = 2.

Примеры тестов

Стандартный вход Стандартный выход
1
5 0
2 -4 5 -1 7
11
2
5 1
2 -4 5 -1 7
4
3
5 2
2 -4 5 -1 7
0

0.828s 0.015s 33