Пачки тестов
Тесты проверяются по порядку, один за другим. Их делят на пачки из подряд идущих тестов; каждая пачка — один запуск песочницы: сначала S мс на запуск, потом тесты пачки по очереди. Вердикты всех тестов пачки появляются в момент, когда пачка закончилась. Первая пачка начинается в момент 0, каждая следующая — сразу после предыдущей.
Разбейте тесты на пачки так, чтобы сумма моментов появления вердиктов всех тестов была наименьшей, и выведите эту сумму.
Третий тест — 1776 запусков эталонных решений каталога в порядке проверки, со временами из замера 17.10.2026; четвёртый — они же по кругу, двести тысяч.
Вход
В первой строке n и S (1 ≤ n ≤ 2 · 10⁵, 0 ≤ S ≤ 1000). Во второй — n времён тестов t1, …, tn в миллисекундах (1 ≤ ti ≤ 1000).
Выход
Наименьшая сумма моментов, в миллисекундах. Она помещается в 64 бита.
Примеры
Пример 1
5 10 5 1 3 2 8
123
Пример 2
4 100 1 1 1 1
416
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Момент вердикта зависит от всех пачек до него, и считать его в лоб неудобно. Посмотрите иначе: на сколько вердиктов увеличивает сумму одна пачка?
2Подсказка 2
Пачка из тестов j + 1 … i длится S + Ti − Tj, где T — префиксные суммы времён, и сдвигает вердикты всех тестов после j. Отсюда динамика по последнему разрезу. Перебирать все j — 2 · 10¹⁰ шагов. Что за функция от Ti стоит под минимумом при фиксированном j?
3Идея
best[i] = minj < i best[j] + (S + Ti − Tj) · (n − j). При фиксированном j это прямая от x = Ti с наклоном n − j. Наклоны убывают, x растёт — огибающая прямых в деке.
4Разбор
На шаге i добавляем в конец дека прямую j = i − 1, выбрасывая сзади прямые, которые она сделала лишними: b лишняя между a и c, если (bc − ba)(ka − kb) ≤ (bb − ba)(ka − kc). Потом сдвигаем начало дека, пока следующая прямая в точке Ti не выше передней, и берём значение передней. Хранить весь массив best не нужно: прямая строится из последнего значения.
4+Решение
5Сложность
O(n): каждая прямая входит в дек и выходит из него не больше раза. Ответ не больше n · (nS + Tn) ≈ 8 · 10¹³.
6Типичные ошибки
- Перебор последнего разреза. Это
wrong.py: на 1776 тестах каталога он справляется, на двухстах тысячах — нет. - Жадность. «Резать, когда пачка длиннее S» или «пачки одной длины» — не оптимально: лучшие пачки в начале большие, а в конце маленькие, потому что пачка в начале задерживает всех.
- Прямая после запроса. Если добавить прямую i − 1 уже после запроса i, теряется вариант «последняя пачка — один тест».
- S = 0. Тогда каждый тест — своя пачка, и ответ — сумма префиксных сумм; дек справляется и с этим, но проверьте, что равные значения не ломают сравнения.