Codeforces Round 909 (Div. 3) |
---|
Закончено |
Лёша участвует в съёмке очередного ролика BrMeast, и BrMeast попросил Лёшу подготовить 250 тысяч тонн тротила, но Лёша его не расслышал, поэтому он подготовил $$$n$$$ коробок. Лёша хочет погрузить эти коробки в грузовики, для этого он расставил их в ряд, $$$i$$$-я слева коробка имеет вес $$$a_i$$$ тонн.
Все грузовики, которые собирается использовать Лёша, вмещают в себя одинаковое количество коробок, обозначим это количество $$$k$$$. Тогда погрузка происходит следующим образом:
По окончании погрузки в каждом грузовике должно быть ровно $$$k$$$ коробок. То есть, если в какой-то момент в грузовик не получится загрузить ровно $$$k$$$ коробок, то вариант погрузки с таким $$$k$$$ невозможен.
Лёша ненавидит справедливость, так что он хочет, чтобы максимальная абсолютная разница между суммарным весом каких-либо двух грузовиков была как можно больше. Если грузовик один, эта величина равна $$$0$$$.
У Лёши есть достаточно много связей, поэтому для каждого $$$1 \leq k \leq n$$$ он может найти такую компанию, что каждый её грузовик вмещает в себя ровно $$$k$$$ коробок. Выведите максимальную абсолютную разницу между суммарным весом каких-либо двух грузовиков.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 150\,000$$$) — количество коробок.
Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — веса коробок.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$150\,000$$$.
Для каждого набора данных выведите одно число — ответ на задачу.
521 2610 2 3 6 1 341000000000 1000000000 1000000000 10000000001560978 82265 78961 56708 39846 31071 4913 4769 29092 91348 64119 72421 98405 222 14294819957 69913 37531 96991 57838 21008 14207 19198
1 9 0 189114 112141
В первом случае выгодно взять два грузовика, в первом будет только первая коробка, во втором только вторая.
Во втором случае выгодно взять шесть грузовиков, в каждом по одной коробке. Тогда максимум равен $$$10$$$, минимум равен $$$1$$$, ответ равен $$$10 - 1 = 9$$$.
В третьем случае при любом возможном $$$k$$$ в грузовиках будет одинаковый суммарный вес коробок, то есть ответ равен $$$0$$$.
Название |
---|