В процессе подготовки к ЕГЭ по Информатике Мишка решает разные задачи не только с предыдущих ЕГЭ по информатике, но и на сайте CodeForces. Пару дней столкнулся с
такой задачей на динамическое программирование.
Мы с ним совместными усилиями придумали алгоритм, но он не работал. Сначала он писал
Превышено ограничение времени на тесте 6, потом
Неправильный ответ на тесте 6.
Я подключился на Java, но тоже отвалился
по времени на тесте 6. Потом подумал и объединил два вызова print - это позволило мне отвалиться
по времени на тесте 8. Это показало мне, что алгоритм правильный и, в результате, я добился
полного решения. Использование
StringBuilder и одного вызова
print сильно ускорило приложение за счёт использования памяти.
После этого я долго пытался понять, что не так с его кодом на C. И всё-таки нашёл ошибку - он выводит результат в формате
"%d ". И заменой его на
"%lld " я получил
полное решение.