OSU!#207

OSU! (Розбір)

Задача розв'язується одним проходом — достатньо акуратно відстежувати два лічильники: суму балів поточної гри та кількість промахів поспіль.

Ідемо по балах a_1, \ldots, a_n і для кожного:

  • додаємо a_i до суми поточної гри;

  • якщо a_i = 0, збільшуємо лічильник промахів поспіль, інакше обнуляємо його;

  • якщо промахів поспіль стало три, гра завершилась: оновлюємо максимум набраним рахунком, обнуляємо суму та лічильник промахів.

Зверніть увагу, що бали за три фатальні нулі дорівнюють нулю, тому додавання їх до суми нічого не псує; рахунок програної гри — це все, що Костя встиг набрати до кінця, як і показано в поясненні до умови.

Тепер про кількість ігор — саме тут найлегше помилитися. Нова гра починається лише тоді, коли після завершення попередньої залишилися ще бали. Тому зручно рахувати так: кількість ігор дорівнює кількості завершених ігор плюс одиниця, якщо після останнього завершення лишився непорожній «хвіст» балів. Якщо ж послідовність закінчується рівно на третьому промаху, додаткової гри не було, і додавати одиницю не треба.

Останню, незавершену гру теж треба врахувати при пошуку максимуму — не забудьте порівняти її суму з поточним максимумом після виходу з циклу.

Складність — .