Вася и его друзья очень любят вкусно поесть. На свой день рождения каждый обязан удивить других, приготовив новые вкусные и полезные блюда.
Сегодня у Васи день рождения, и он позвал своих друзей отведать $$$n$$$ своих самых лучших блюд. Название каждого из них состоит из строчных букв английского алфавита, цифр и знака подчёркивания.
Для приготовления блюда с номером $$$i$$$ требуется $$$z_i$$$ ингредиентов. Для каждого ингредиента известно его название, требуемое количество для одной порции блюда, а также единица измерения, в которой это количество задано. Помимо этого, Васе известно, что $$$i$$$-й кулинарный шедевр захотят попробовать $$$c_i$$$ друзей.
Используются следующие единицы измерения:
- g, kg – граммы и килограммы соответственно;
- l, ml – литры и миллилитры соответственно;
- cnt, tens – одна штука и десять штук соответственно.
В одном килограмме $$$1000$$$ грамм и в одном литре $$$1000$$$ миллилитров. Делать перевод из одной единицы измерения в другую можно тогда и только тогда, когда они одновременно обозначают или массу, или объём, или количество.
У Васи есть два справочника ингредиентов. В первом для каждого ингредиента указано его количество в упаковке и цена за упаковку. Во втором справочнике для каждого ингредиента указано содержание белков, жиров, углеводов и энергетическая ценность некоторого количества данного ингредиента.
Васе нужно приготовить все блюда, при этом не купить ничего лишнего. Для этого ему нужно определить, какие ингредиенты и в каком количестве необходимо приобрести в магазине.
Так как друзья именинника очень следят за питанием, то они, перед тем как попробовать Васины блюда, захотят узнать всё: как Вася готовил блюда, их энергетическую ценность и содержание белков, жиров и углеводов. Васе нужно подготовить эту информацию.
Необходимо помочь имениннику подсчитать, сколько требуется потратить денег на покупку продуктов в магазине, какие ингредиенты и в каком количестве нужно купить, а также для каждого блюда посчитать содержание белков, жиров, углеводов и энергетическую ценность, если его съесть полностью.
Первая строка содержит целое число $$$n$$$ ($$$1 \leqslant n \leqslant 1000$$$) — количество блюд, которое решил приготовить Вася.
Затем следует описание $$$n$$$ блюд. В первой строке содержатся строка $$$d_i$$$ и целые числа $$$c_i$$$, $$$z_i$$$ ($$$1 \leqslant c_i, z_i \leqslant 100$$$) — название блюда, количество друзей, желающих отведать данное блюдо, и количество ингредиентов необходимых для приготовления. Название блюда состоит из строчных букв английского алфавита, цифр и знака подчёркивания. Его длина не превосходит $$$20$$$ символов.
В следующих $$$z_i$$$ строках содержатся описания ингредиентов. В строке с номером $$$j$$$ содержатся строка $$$s_{i, j}$$$ — название ингредиента, целое число $$$a_{i, j}$$$ ($$$1 \leqslant \text{a}_{i, j} \leqslant 1000$$$) — требуемое количество ингредиента и строка $$$\text{u}_{i, j}$$$ — название единицы измерения количества. Название ингредиента состоит из строчных букв английского алфавита, цифр и знака подчёркивания. Длина строки не превосходит $$$20$$$ символов.
Следующая строка содержит целое число $$$k$$$ ($$$1 \leqslant k \leqslant 1000$$$) — количество ингредиентов в каталоге цен.
В каждой из следующих $$$k$$$ строк, содержатся четыре значения $$$t_i\,p_i\,a_i\,u_i$$$, описывающих ингредиент.
- $$$t_i$$$ — название ингредиента, состоящее из строчных букв английского алфавита, цифр и знака подчёркивания. Длина строки не превосходит $$$20$$$ символов;
- $$$p_i$$$ — стоимость ингредиента, заданная целым числом ($$$1 \leqslant p_i \leqslant 1000$$$);
- $$$a_i$$$ — количество ингредиента в упаковке в единицах, заданное целым числом ($$$1 \leqslant a_i \leqslant 1000$$$);
- $$$u_i$$$ — единица измерения количества (l, ml, g, kg, cnt или tens);
Следующая строка содержит число $$$m$$$ ($$$1 \leqslant m \leqslant 1000$$$) — количество ингредиентов в каталоге еды.
Далее расположены $$$m$$$ строк, в каждой из которой содержится семь значений $$$t_i\,a_i\,u_i\,pr_i\,f_i\,ch_i\,fv_i$$$, описывающих ингредиент.
- $$$t_i$$$ — название ингредиента, состоящее из строчных букв английского алфавита, цифр и знака подчёркивания. Длина строки не превосходит $$$20$$$ символов;
- $$$a_i$$$ — количество ингредиента, для которого указаны характеристики ингредиента, заданное целым числом ($$$1 \leqslant a_i \leqslant 1000$$$);
- $$$u_i$$$ — единица измерения (l, ml, g, kg, cnt или tens);
- $$$pr_i$$$, $$$f_i$$$, $$$ch_i$$$, $$$fv_i$$$ — содержание белков, жиров, углеводов и энергетическая ценность ингредиента, соответственно, заданные вещественными числами с не более чем шестью знаками после запятой ($$$0 \leqslant pr_i, f_i, ch_i \leqslant 1000, 0 \leqslant fv_i \leqslant 10000$$$).
Гарантируется, что:
- в каталогах перечислены все ингредиенты, необходимые для приготовления блюд;
- не существует двух блюд с одинаковым названием;
- не существует двух ингредиентов в одном каталоге с одинаковым названием;
- не существует двух ингредиентов в одном блюде с одинаковым названием;
- для любых двух упоминаний ингредиента единицы измерения, в которых заданы его количества, можно перевести друг в друга.
Первая строка должна содержать одно целое число: сумма, которую нужно потратить Васе на подготовку к празднику.
Далее должны следовать $$$k$$$ строк, в каждой из которых через пробел указано название ингредиента и целое число — количество упаковок, которое необходимо купить. Ингредиенты, выведенные в этих $$$k$$$ строках должны соответствовать ингредиентам, описанным в первом справочнике.
В следующих $$$n$$$ строках через пробел должны быть указаны название блюда и его характеристики, описанные четырьмя вещественными числами: белки, жиры, углеводы и энергетическая ценность.
Ингредиенты и блюда разрешается выводить в любом порядке.
Ваш ответ будет считаться правильным, если все целые числа совпадают с соответствующими числами в ответе жюри, а для всех вещественных чисел в ответе их абсолютная или относительная погрешность не превосходит $$$10^{-3}$$$. Более формально, пусть вещественное число в вашем ответе равно $$$A$$$, а соответствующее число в ответе жюри равно $$$B$$$. Тогда число $$$A$$$ будет считаться корректным, если $$$\frac{|A-B|}{\max(1,B)} \leq 10^{-3}$$$.
2 sandwich 7 3 butter 10 g toasted_bread 2 cnt sausage 30 g omelet 9 4 egg 4 cnt milk 120 ml salt 1 g sausage 50 g 7 egg 61 1 tens milk 58 1 l sausage 100 480 g butter 120 180 g cream 100 350 g salt 14 1000 g toasted_bread 40 20 cnt 8 egg 1 cnt 13 12 1 16.4 milk 1 l 3 4.5 4.7 60 chocolate 90 g 6.8 36.3 47.1 546 salt 1 kg 0 0 0 0 strawberry 100 g 0.4 0.1 7 35 sausage 100 g 10 18 1.5 210 toasted_bread 5 cnt 7.3 1.6 52.3 248 butter 100 g 0.8 72.5 1.3 661
734 egg 4 milk 2 sausage 2 butter 1 cream 0 salt 1 toasted_bread 1 sandwich 6.00 13.29 21.50 228.3 omelet 57.360 57.540 5.314 177.800
В первом примере Васе необходимо приготовить $$$7$$$ бутербродов и $$$9$$$ омлетов.
Для приготовления всех первых блюд необходимо $$$10 \cdot 7$$$ грамм масла, $$$2 \cdot 7$$$ кусочков хлеба и $$$30 \cdot 7$$$ грамм колбасы. В каждом из бутерброде будет содержаться $$$0.8 \cdot \frac{10}{100} + 7.3 \cdot \frac{2}{5} + 10 \cdot \frac{30}{100} = 6$$$ грамм белков, $$$72.5 \cdot \frac{10}{100} + 1.6 \cdot \frac{2}{5} + 18 \cdot \frac{30}{100} = 13.29$$$ грамм жиров и $$$1.3 \cdot \frac{10}{100} + 52.3 \cdot \frac{2}{5} + 1.5 \cdot \frac{30}{100} = 21.5$$$ грамм углеводов. Энергетическая ценность составит $$$661 \cdot \frac{10}{100} + 248 \cdot \frac{2}{5} + 210 \cdot \frac{30}{100} = 228.3$$$ ккал.
Для приготовления всех вторых блюд необходимо $$$4 \cdot 9 = 36$$$ яиц, $$$120 \cdot 9 = 1080$$$ миллилитров молока, $$$9$$$ грамм соли, $$$50 \cdot 9 = 450$$$ грамм колбасы. В каждом омлете будет содержаться $$$13 \cdot 4 + 3 \cdot \frac{120}{1000} + 10 \cdot \frac{50}{100} = 57.36$$$ грамм белков, $$$12 \cdot 4 + 4.5 \cdot \frac{120}{1000} + 18 \cdot \frac{50}{100} = 57.54$$$ жиров и $$$1 \cdot 4 + 4.7 \cdot \frac{120}{1000} + 1.5 \cdot \frac{50}{100} = 5.314$$$ углеводов. Энергетическая ценность составит $$$16.4 \cdot 4 + 60 \cdot \frac{120}{1000} + 210 \cdot \frac{50}{100} = 177.8$$$ ккал.
Всего необходимо $$$70$$$ грамм масла, $$$36$$$ яиц, $$$1080$$$ литров молока, $$$9$$$ грамм соли, $$$210 + 450 = 660$$$ грамм колбасы и $$$14$$$ кусочков тостового хлеба.
Таким образом, в магазине нужно купить одну упаковку масла, $$$4$$$ десятка яиц, $$$2$$$ упаковки колбасы и молока, по одной упаковке соли и тостового хлеба, заплатив $$$120 + 61 \cdot 4 + 100 \cdot 2 + 58 \cdot 2 + 14 + 40 = 734$$$ рубля.
Во всех крупных IT-компаниях немалое внимание уделяется вопросам информационной безопасности, и Яндекс — не исключение.
Дима и Егор разрабатывают новый сервис YD (Yandex Dorogi) и в данный момент проводят аудит его безопасности. Для шифрования пользовательских данных в YD используется алгоритм шифрования с открытым ключом YS (Yandex Shifrovatel).
Схема работы YS такова: для каждого сервиса генерируется закрытый ключ ($$$p, q$$$), где $$$p$$$ и $$$q$$$ — натуральные числа. По закрытому ключу ($$$p, q$$$) генерируется открытый ключ (НОД($$$p, q$$$), НОК($$$p, q$$$)), который доступен всем пользователям. Если злоумышленник сможет по открытому ключу получить закрытый ключ, то он получит доступ ко всем данным YD и принесет сервису непоправимый вред. Конечно же, Егор и Дима не могут этого допустить, поэтому они хотят сделать так, чтобы злоумышленнику пришлось перебрать очень много вариантов открытого ключа, прежде чем он сможет его угадать.
Дима уже сгенерировал закрытый ключ для YD и получил на его основе открытый ключ ($$$x, y$$$). Егору сразу же стало интересно, сколько вариантов закрытого ключа придётся перебрать злоумышленнику для взлома YD в худшем случае, иными словами, сколько существует закрытых ключей ($$$p, q$$$), таких, что открытым ключом для них является ($$$x, y$$$). К сожалению, у Егора есть много других задач, очень важных для запуска YD, поэтому он просит вас вычислить это количество за него.
В первой строке содержатся два целых числа $$$x$$$ и $$$y$$$ ($$$1 \leq x \leq y \leq 10^{12}$$$) — описание открытого ключа.
Выведите одно целое число — количество закрытых ключей, для которых данный ключ является открытым.
5 10
2
10 11
0
527 9486
4
В первом примере существует два закрытых ключа, для которых ($$$5, 10$$$) является открытым ключом: ($$$5, 10$$$) и ($$$10, 5$$$).
Во втором примере Дима ошибся, потому что ни один закрытый ключ не порождает открытый ключ ($$$10, 11$$$).
В третьем примере подходящими закрытыми ключами являются ($$$527, 9486$$$), ($$$1054, 4743$$$), ($$$4743, 1054$$$), ($$$9486, 527$$$).
НОД (наибольшим общим делителем) двух натуральных чисел $$$p$$$ и $$$q$$$ называется наибольшее число $$$k$$$, такое, что $$$p$$$ делится на $$$k$$$ и $$$q$$$ делится на $$$k$$$. Например, НОД($$$6, 15$$$) равен $$$3$$$, а НОД($$$16, 8$$$) равен $$$8$$$.
НОК (наименьшим общим кратным) двух натуральных чисел $$$p$$$ и $$$q$$$ называется наименьшее число $$$k$$$, такое, что $$$k$$$ делится на $$$p$$$ и $$$k$$$ делится на $$$q$$$. Например, НОК($$$2, 3$$$) равен $$$6$$$, а НОК($$$10, 20$$$) равен 20.
Однажды программист Алексей из Яндекса взял отпуск и уехал отдыхать на море. В один из дней он пошёл на пляж, причём пошёл туда не один. Возможно, он пошёл туда с мамой, возможно, с бабушкой, а, возможно, с другом или подругой. Важно, что пошёл он туда не один.
На пляже программист Алексей обнаружил, что осталось всего $$$n$$$ ($$$2 \leq n \leq 10^6$$$) свободных лежаков. Но среди всего этого множества лежаков программисту Алексею нужно было всего лишь 2: для него самого и для того (или той), с кем он пришёл. Так как программист Алексей очень любил порядок, то он хотел, чтобы лежаки были как можно более похожи друг на друга. Похожесть лежаков можно вычислить следующим образом:
- Каждому лежаку каким-то образом по его внешним признакам назначается некоторое число $$$a_i$$$ ($$$1 \leq i \leq n$$$, $$$0 \leq a_i \leq 10^9$$$).
- Затем непохожесть двух лежаков вычисляется как XOR (побитовое исключающее ИЛИ) чисел назначенных этим лежакам. Чем значение непохожести меньше, тем более похожи лежаки.
Помогите программисту Алексею понять, какого минимального значения непохожести лежаков он может достичь, сравнив попарно все свободные лежаки.
В первой строке задано число $$$T$$$ ($$$1 \leq T \leq 1000$$$) – количество тестов. Каждый тест состоит из двух строк.
В первой строке каждого теста задано число $$$n$$$ ($$$2 \leq n \leq 10^6$$$) – количество лежаков.
Во второй строке каждого теста заданы $$$n$$$ чисел $$$a_i$$$ ($$$1 \leq i \leq n$$$, $$$0 \leq a_i \leq 10^9$$$) – значения, которые были поставлены лежакам в соответствие по внешним признакам.
Сумма $$$n$$$ по всем тестам не превосходит $$$10^6$$$.
Для каждого теста выведите по одной строке, в которой должно быть единственное число – минимальное значение непохожести.
1 5 1 2 4 8 16
3
2 2 2 4 4 2 4 6 8
6 2
В первом примере Алексей выберет лежаки со значениями 1 и 2.
В первой части второго примера Алексей может взять только лежаки со значениями 2 и 4. Во второй части он выберет лежаки со значениями 4 и 6.
Хранение данных в распределённом хранилище является крайне сложной задачей, однако инженеры ОАО "Быки и Коровы" успешно с ней справляются.
Один из кластеров хранилища состоит из $$$m$$$ серверов, на которых хранятся данные, разбитые на $$$n$$$ чанков. Для дефрагментации кластера и возможности отключения старых серверов чанки периодически приходится перемещать между серверами. Перемещение чанков по одному неэффективно, поэтому они перемещают группами. Запрос на перемещение описывается четырьмя числами $$$a, b, l, r$$$ и обозначает заказ на перемещение всех чанков с номерами от $$$l$$$ до $$$r$$$ включительно с сервера с номером $$$a$$$ на сервер с номером $$$b$$$. После перемещения соотвествующие чанки с сервера с номером $$$a$$$ стираются. Таким образом, каждый чанк находится всегда ровно на одном сервере.
При построении распределённых систем очень важно избегать возможности конфликта изменений на кластере. Перед выполнением каждого из запросов необходимо убедиться, что все чанки, участвующие в запросе, находятся на ожидаемом сервере. Иными словами, перед выполнением запроса, описываемого параметрами $$$a, b, l, r$$$, необходимо убедиться, что все чанки с номерами от $$$l$$$ до $$$r$$$ включительно расположены на сервере с номером $$$a$$$. В случае, если это неверно, запрос на перемещение чанков отменяется и система переходит к обработке следующего запроса. Если же это верно, то запрос осуществляется и все чанки от $$$l$$$ до $$$r$$$ включительно перемещаются с сервера $$$a$$$ на сервер $$$b$$$.
По заданному начальному состоянию кластера и списку запросов перемещения чанков определите, какие запросы будут выполнены.
В первой строке заданы три целых числа $$$n, m$$$ и $$$q$$$ ($$$1 \leq n, q \leq 100\,000, 2 \leq m \leq 100\,000$$$) — количество чанков на кластере, количество серверов, на которых располагаются чанки, и количество запросов, соответственно.
Во второй строке содержатся $$$n$$$ чисел $$$p_i$$$ ($$$1 \leq p_i \leq m$$$), $$$i$$$-е из которых обозначает номер сервера, где изначально располагается чанк с номером $$$i$$$.
В следующих $$$q$$$ строках содержатся описания запросов перемещения чанков в хронологическом порядке.
Каждый запрос описывается четвёркой чисел $$$a_i, b_i, l_i, r_i$$$ ($$$1 \leq a_i, b_i \leq m, a_i \neq b_i, 1 \leq l_i \leq r_i \leq n$$$) и обозначает заказ на перемещение чанков с номерами с $$$l_i$$$ по $$$r_i$$$ (включительно) с сервера $$$a_i$$$ на сервер $$$b_i$$$.
Выведите $$$q$$$ строк. В строке с номером $$$i$$$ выведите $$$1$$$, если запрос с номером $$$i$$$ будет выполнен, и $$$0$$$, если нет.
1 2 1 1 1 2 1 1
1
1 2 1 1 2 1 1 1
0
5 5 6 1 2 3 4 5 1 2 1 1 2 3 1 3 4 2 4 4 2 5 1 4 3 2 2 3 3 2 3 3
1 0 1 0 0 1
Рассмотрим третий пример. Изначально расположение чанков на серверах описывается массивом $$$[1, 2, 3, 4, 5]$$$.
В первом запросе требуется переместить чанк с номером $$$1$$$ с сервера $$$1$$$ на сервер $$$2$$$. Чанк с номером $$$1$$$ находится на сервере $$$1$$$, поэтому перемещение будет произведено. После выполнения запроса расположение чанков на серверах описывается массивом $$$[2, 2, 3, 4, 5]$$$.
Во втором запросе требуется переместить чанки $$$1, 2$$$ и $$$3$$$ с сервера $$$2$$$ на сервер $$$3$$$. Чанк $$$3$$$ расположен не на сервере $$$2$$$, а на сервере $$$3$$$, поэтому операция не будет выполнена. Расположение чанков на серверах останется прежним.
В третьем запросе требуется переместить чанк $$$4$$$ с сервера $$$4$$$ на сервер $$$2$$$. Чанк $$$4$$$ находится на сервере $$$4$$$, поэтому перемещение будет произведено. После выполнения запроса расположение чанков на серверах будет описываться массивом $$$[2, 2, 3, 2, 5]$$$.
В четвёртом запросе требуется переместить чанки $$$1, 2, 3$$$ и $$$4$$$ с сервера $$$2$$$ на сервер $$$5$$$. Так как чанк $$$3$$$ расположен на сервере $$$3$$$, а не на сервере $$$2$$$, запрос не будет выполнен и расположение чанков останется прежним.
В пятом запросе требуется переместить чанки $$$2$$$ и $$$3$$$ с сервера $$$3$$$ на сервер $$$2$$$, но чанк $$$2$$$ расположен на сервере $$$2$$$, поэтому запрос не будет выполнен и расположение чанков останется прежним.
В шестом запросе требуется переместить чанк $$$3$$$ с сервера $$$3$$$ на сервер $$$2$$$. Чанк с номером $$$3$$$ находится на сервере $$$3$$$, поэтому перемещение будет произведено и расположение чанков станет описываться массивом $$$[2, 2, 2, 2, 5]$$$.
Дан взвешенный неориентированный граф $$$G$$$, содержащий $$$n$$$ вершин и $$$m$$$ ребер.
Разбейте вершины графа на два не пустых множества так, чтобы ребро минимального веса, соединяющее вершины из одного множества, имело максимально большой вес.
Гарантируется, что граф не содержит петель и его нельзя разбить так, чтобы такого ребра не существовало.
В первой строке задано число вершин $$$n$$$ ($$$3 \leq n \leq 10^5$$$) и число ребер $$$m$$$ ($$$3\leq m \leq 10^5$$$) графа.
В следующих $$$m$$$ строках заданы ребра в формате $$$u$$$, $$$v$$$, $$$w$$$ ($$$1\leq u, v \leq n$$$, $$$u\neq v$$$, $$$1 \leq w \leq 10^5$$$), где $$$u$$$ и $$$v$$$ задают начальную и конечную вершину ребра, а $$$w$$$ — его вес.
В единственной строке выведите максимальный возможный вес ребра, которое имеет минимальный вес среди тех, что соединяют вершины, принадлежащие одному множеству.
3 4 1 2 1 1 2 2 1 3 3 3 2 4
4
4 5 1 2 1 2 3 1 3 4 1 4 1 1 2 4 2
2
Рассмотрим первый пример из условия. В нём возможно всего 3 различных разбиения, удовлетворяющих условию, рассмотрим каждое из них:
- $$$\{\{1, 2\}, \{3\}\}$$$, в таком случае рёбра $$$1$$$ и $$$2$$$ будут будут соединять вершины из одного множества, то есть ответ $$$1$$$;
- $$$\{\{1, 3\}, \{2\}\}$$$, в таком случае только ребро $$$3$$$ будет соединять вершины из одного множества, то есть ответ $$$3$$$;
- $$$\{\{2, 3\}, \{1\}\}$$$, в таком случае только ребро $$$4$$$ будет соединять вершины из одного множества, то есть ответ $$$4$$$.
Получаем, что ответ на тест достигается при третьем варианте разбиения.
Во втором тесте ответ достигается на разбиении $$$\{\{1, 3\}, \{2, 4\}\}$$$. Легко убедиться, расписав все возможные разбиения, что не существует разбиения данного графа, на котором ответ был бы больше.
Разработчики Яндекс.Поиска постоянно работают над улучшением алгоритмов ранжирования. Один из алгоритмов, который хотят опробовать, таков.
Поисковый алгоритм состоит из трёх этапов: поиск по базе, отбор документов и фильтрация. Во время поиска по базе отбираются $$$n$$$ документов-кандидатов для показа пользователю. Каждому документу сопоставляется целое число — релевантность, показывающее, насколько документ подходит пользователю. Чем выше релевантность, тем лучше документ подходит по данному запросу. Обратите внимание, что релевантность может быть даже отрицательной в случае, если документ не имеет никакого отношения к запросу.
Ранжирующий алгоритм хранит данные в закольцованном списке, таким образом, после документа с номером $$$i$$$ ($$$i \lt n$$$) следующим в списке является документ с номером $$$i + 1$$$, а следующим после документа с номером $$$n$$$ будет документ с номером $$$1$$$. Во время отбора документов алгоритм выберет некоторый документ (назовём его начальным) и сколько-то следующих за начальным документов, которые будут переданы на фильтрацию.
Во время фильтрации из списка документов, полученных при отборе, может быть удалено несколько документов, но не более $$$k$$$. Кроме того, после фильтрации должен остаться хотя бы один документ. Оставшиеся после фильтрации документы показываются пользователю.
Релевантностью выдачи назовём сумму релевантностей документов в ней. По релевантностям документов, полученных во время поиска, определите, какую наибольшую релевантность выдачи можно получить при оптимальной работе алгоритма.
В первой строке задано целое число $$$t$$$ — количество тестовых случаев. Далее следует описание тестовых случаев.
Описание каждого теста состоит из двух строк.
В первой строке задано два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 100\,000$$$, $$$0 \leq k \leq min(n - 1, 100)$$$) — количество документов, полученных во время поиска, и максимальное количество документов, которые могут быть удалены после фильтрации соответственно.
Во второй строке содержатся $$$n$$$ целых чисел $$$a_i$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — релевантности документов.
Гарантируется что сумма $$$n$$$ по всем тестовым случаям не превосходит $$$100\,000$$$.
Для каждого тестового случая выведите одно целое число — ответ на задачу.
64 01 -2 9 106 15 -5 5 -5 5 -56 25 -5 5 -5 5 -54 35 -5 5 -58 1-3 -1 5 6 -200 -200 5 -13 1-1 -2 -3
20 10 15 10 14 -1
В первом примере выгодно выбрать в качестве начального документ с релевантностью $$$9$$$ и отправить на фильтрацию его и следующие 2 документа. На стадии фильтрации необходимо оставить все документы.
Во втором примере выгодно выбрать в качестве начального любой документ с релевантностью $$$5$$$, отправить на стадию фильтрации его и следующие за ним 2 документа. На стадии фильтрации необходимо удалить документ с релевантностью $$$-5$$$, таким образом, на выдачу попадут два документа с релевантностью $$$5$$$.
В пятом примере выгодно выбрать в качестве начального документ с номером $$$7$$$ и отправить на стадию фильтрации его и следующие $$$5$$$ документов. Таким образом, на стадию фильтрации попадут документы с релевантностями $$$[5, -1, -3, -1, 5, 6]$$$. На стадии фильтрации выгодно удалить документ с релевантностью $$$-3$$$, в результате чего на выдачу попадут документы с релевантностями $$$[5, -1, -1, 5, 6]$$$ с суммарной релевантностью $$$14$$$.
В последнем примере релевантность выдачи получится отрицательной, так как пользователю необходимо показать хотя бы один документ.