| Автор: | Иван Кобец, Артем Завгороднев | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
На лекции по высшей математике в ДВФУ преподаватель собрал n студентов в ряд и задал простой вопрос: Кто сейчас грустит, поднимите руку. На это предложение несколько (возможно, ноль) студентов подняли руки.
После этого, он решил выбрать из этой последовательности студентов некоторый отрезок [left, right], на котором он добавит грустным студентам по 5 баллов к экзамену просто так. При этом, он понимает, что студенты, которые были радостные на этом отрезке, поменяют своё настроение. Если ни один студент не является грустным, преподаватель не будет выбирать никакой отрезок. Он хочет получить наибольшее количество радостных студентов на лекции, поэтому просит Вас написать программу, которая рассчитает максимальное их количество после применения ранее описанной операции.
В первой строке записано целое число n — количество студентов.
Во второй строке записано n цифр 0 и 1, где 0 — грустный студент, а 1 — радостный
Выведите максимально возможное количество радостный студентов.
1 ≤ n ≤ 2 ⋅ 105
Баллы начисляются за каждый тест независимо. Тесты поделены по подзадачам, описанным ниже.
| Подзадача | Количество тестов | Баллы | Дополнительные ограничения | Информация о проверке |
|---|---|---|---|---|
| n | ||||
| 1 | 5 тестов | 5 баллов за тест | 1 ≤ n ≤ 200 | полная |
| 2 | 5 тестов | 5 баллов за тест | 1 ≤ n ≤ 2000 | полная |
| 3 | 10 тестов | 5 баллов за тест | 1 ≤ n ≤ 2 ⋅ 105 | полная |
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|
Идеей решения данного задания - линейный поиск максимальной суммы подотрезка.
Посчитаем первоначальное количество радостных студентов. Следующим шагом (или параллельно) создадим массив, содержащий изменения настроения студентов, если они войдут в подотрезок профессора. Радостных студентов обозначим как -1 (настроение станет негативным), а грустных как 1 (настроение станет позитивным).
Следующим шагом создадим две переменные, в которых будут хранится сумма изменений студентов на некотором отрезке [1, i] и сумма изменений настроений на некотором отрезке [1, j], j < i ≤ n. Параметр j будет на каждом шагу выбираться так, чтобы сумма отрезка [1, j] являлась наименьшей на отрезке [1, i]. Отрезок минимальной суммы будет убираться из отрезка общей суммы sum[1, i] − sum[1, j], тем самым мы сможем получить наибольшую сумму изменений настроений студентов. Так как мы изначально сделали радостных студентов -1, а грустных 1, процесс вычисления будет стараться избегать случаем, когда изменится настроение у позитивных студентов, но при этом будет искать наибольшее количество грустных студентов и компенсировать настроение новоиспеченных грустных студентов.
Среди всех подотрезков выберем тот, у которого наибольшее изменение настроений и добавим к уже ранее высчитанным радостным студентам, и выведем полученную сумму. Данный результат будет верным, ведь если изменится настроение у радостного студента, наш подотрезок будет это учитывать. Например, если на подотрезке 3 грустных студента и 1 радостный, то сумма настроений на подотрезке будет 2 (двое станут новыми радостными, а оставшиеся два студента, радостный и грустный, компенсируют свои настроения).