Всем привет =) У меня (надеюсь не только у меня) получилось написать оптимизацию решения с бинпоиском за nmlogn с уменьшением границ.

К примеру левая граница = max(answ, максимальный по длине переход * расход топлива, всего путь /(остановки+1)+1);

answ — это максимум прошлых запросов

r надо брать min(всего путь * на расход, кол-во городов на пути / (кол-во остановок я могу сделать+1) * макс переход))

К сожалению в r есть переполнение.. на контесте я это не заметил =( для AC надо писать вот так:

r = min(всего путь * на расход, min(кол-во городов на пути / (кол-во остановок я могу сделать+1), inf/макс длина за один переход * расход) * макс переход))

Работает очень быстро вот код:

http://mirror.codeforces.com/contest/1101/submission/48293038

Кто нибудь может сказать асимптотику такого решения?? буду благодарен =)!