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

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

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

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

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

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

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

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

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