CodeForces

В процессе подготовки к ЕГЭ по Информатике Мишка решает разные задачи не только с предыдущих ЕГЭ по информатике, но и на сайте CodeForces. Пару дней столкнулся с такой задачей на динамическое программирование.

Мы с ним совместными усилиями придумали алгоритм, но он не работал. Сначала он писал Превышено ограничение времени на тесте 6, потом Неправильный ответ на тесте 6.

Я подключился на Java, но тоже отвалился по времени на тесте 6. Потом подумал и объединил два вызова print - это позволило мне отвалиться по времени на тесте 8. Это показало мне, что алгоритм правильный и, в результате, я добился полного решения. Использование StringBuilder и одного вызова print сильно ускорило приложение за счёт использования памяти.

После этого я долго пытался понять, что не так с его кодом на C. И всё-таки нашёл ошибку - он выводит результат в формате "%d ". И заменой его на "%lld " я получил полное решение.