Ctrl K

Пиковая высота штоков насоса

Сложная
В насосе ходят вверх-вниз несколько штоков. Каждый шток может находиться на высоте от 0 до top. Даны массив levels, где levels[i] — текущая высота штока i, и строка moves, где moves[i] — его направление: 'U' — вверх, 'D' — вниз. Каждую секунду каждый шток сдвигается на 1 в своём направлении. Как только шток оказывается на высоте 0 или top, его направление меняется на противоположное (шток, стоящий на краю и смотрящий наружу, на следующей секунде пойдёт обратно). Верните наибольшую суммарную высоту всех штоков, которая будет когда-либо достигнута, включая текущий момент.
Пример 1
top=4, levels=[1, 3], moves="UD" → 4

Сейчас сумма 1 + 3 = 4, и она не меняется: один шток поднимается, другой опускается, а когда второй отскочит от дна, первый уже отскочит от верха. Ответ 4.

Пример 2
top=5, levels=[0, 2, 5], moves="UUD" → 10

Через 3 секунды штоки на высотах 3, 5 и 2 — сумма 10, больше не бывает.

Пример 3
top=3, levels=[3, 0, 0], moves="DDD" → 6
Ограничения
  • 1 ≤ top ≤ 10⁶
  • 1 ≤ len(levels) = len(moves) ≤ 10⁵
  • 0 ≤ levels[i] ≤ top
  • moves[i] — 'U' или 'D'
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОдинаковые края на отрезках СредняяРавные разрезы после одной замены СложнаяНОД пар по номеру в сортировке СложнаяСамые частые запросы СредняяСводка заходов по доменам Средняя
загружаем Python…
Вход
top=4, levels=[1, 3], moves="UD"
Ожидается
4

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 90 тестов на сервере, включая скрытые.