Решение задачи Сон на лекции с Codeforces
С пояснением   Просмотров: 100
Вы со своим другом Мишкой сидите на лекции по математическому анализу. Лекция длится n минут. Лектор рассказывает a i теорем в течение i-й минуты.
Хотя Мишке очень нравится математический анализ, иногда очень трудно не засыпать во время лекции. Вам задан массив t поведения Мишки. Если он спит в течение i-й минуты лекции, то t i равняется 0, иначе оно равняется 1. Когда Мишка не спит, он записывает все теоремы, которые слышит — a i теорем в течение i-й минуты. Иначе он не записывает ничего.
Вы знаете некоторую секретную технику, при помощи которой можно заставить не спать Мишку в течение k минут подряд. Но вы можете использовать её только один раз. Вы можете начать использовать её в любую минуту с 1 по n - k + 1. Если вы используете её в минуту i, Мишка не будет спать во все такие минуты j, что , и будет записывать все лекции, которые расскажет лектор.
Ваша задача состоит в том, чтобы посчитать, какое максимальное количество теорем Мишка сможет записать, если вы используете секретную технику, чтобы заставить его не спать, только один раз.
Хотя Мишке очень нравится математический анализ, иногда очень трудно не засыпать во время лекции. Вам задан массив t поведения Мишки. Если он спит в течение i-й минуты лекции, то t i равняется 0, иначе оно равняется 1. Когда Мишка не спит, он записывает все теоремы, которые слышит — a i теорем в течение i-й минуты. Иначе он не записывает ничего.
Вы знаете некоторую секретную технику, при помощи которой можно заставить не спать Мишку в течение k минут подряд. Но вы можете использовать её только один раз. Вы можете начать использовать её в любую минуту с 1 по n - k + 1. Если вы используете её в минуту i, Мишка не будет спать во все такие минуты j, что , и будет записывать все лекции, которые расскажет лектор.
Ваша задача состоит в том, чтобы посчитать, какое максимальное количество теорем Мишка сможет записать, если вы используете секретную технику, чтобы заставить его не спать, только один раз.
Пояснение к задаче
Проитерируемся по всем i от 1 до n, и если t i равняется 1, тогда добавим a i к некоторой переменной res и заменим a i на 0. Тогда ответ будет равен , где можно легко посчитать при помощи префиксных сумм для всех i.