Один день - одна задача. Вишневый вопрос
Недавно закончился квалификационный раунд, где командам было предложено 12 задач. Лучшие команды решили все задачи этого раунда, однако были команды, которым это не удалось.Становиться лучше можно путем ежедневных тренировок. Поэтому вы можете участвовать в тренировке на платформе Codeforces c задачами квалификации и решать по одной задачке в день https://codeforces.com/gym/102775
Мы продолжаем наш разбор задачей L. Вишневый вопрос
Для решения задачи воспользуемся методом сканирующей прямой. Событие будут представлять собой пару (день, количество цветков). В список событий будем добавлять только следующие пары:
(ai,ki) – начало цветения и количество появляющихся цветков,
(bi+1, −2 · ki) – первый день увядания
(bi + 2 + |ai − bi|, ki) – день, когда i-е дерево отцветет.
Пройдемся по данному списку событий в порядке возрастания дней и будем поддерживать те- кущее количество цветков на всех вишнях. Для каждого дня (не события) суммируем значения цветков ki (обозначим эту сумму за s), до тех пор, пока не найдем событие, день наступления кото- рого отличается от предыдущих. К этому дню количество цветков равно s, умноженному на разницу дней. Добавим это значение к счетчику цветков на всех вишнях и обновим значение максимума для нашего ответа. Так как мы храним −2 · ki в днях начала увядания, то мы действительно будем поддерживать корректное количество цветков, рассматривая некоторый день.