Пан Бізнесюк мінімізує величину P + K \cdot T, тому зручно одразу перевести весь час у гроші: секунда коштує центів. Тоді проїзд фрагмента безплатною дорогою коштує K \cdot a_i, платною — K \cdot b_i + c_i, а перебудова між дорогами перед фрагментом — K \cdot q_i. Далі мінімізуємо просто суму.
Оскільки на кожному фрагменті є лише два стани (їдемо безплатною чи платною дорогою), напрошується динамічне програмування з двома станами.
Позначимо — мінімальна вартість подолати перші фрагментів так, щоб -й було пройдено безплатною дорогою, і — те саме для платної.
База: \mathrm{dp}[1][0] = K a_1, \mathrm{dp}[1][1] = K b_1 + c_1 (перед першим фрагментом розв'язки немає, почати можна з будь-якої дороги).
Перехід: якщо тип дороги збігається з попереднім, платити за розв'язку не треба, інакше додається K q_i:
Відповідь — \min(\mathrm{dp}[N][0], \mathrm{dp}[N][1]).
Складність — , що з величезним запасом вкладається в N \le 60.
Головна пастка — розмір чисел: a_i, b_i, c_i сягають 10^{12}, а — до , тому добуток доходить до 2 \cdot 10^{15}, а сума по фрагментах — приблизно до 10^{17}. Це вміщується у 64-бітний тип, але не у 32-бітний. Окремо зверніть увагу на K = 0: тоді час не має значення взагалі й лишається мінімізувати самі дорожні збори.