Всем привет =) У меня (надеюсь не только у меня) получилось написать оптимизацию решения с бинпоиском за nmlogn с уменьшением границ.
К примеру левая граница = max(answ, максимальный по длине переход * расход топлива, всего путь /(остановки+1)+1);
answ — это максимум прошлых запросов
r надо брать min(всего путь * на расход, кол-во городов на пути / (кол-во остановок я могу сделать+1) * (макс переход * расход)))
К сожалению в r есть переполнение.. на контесте я это не заметил =( для AC надо писать вот так:
r = min(всего путь * на расход, min(кол-во городов на пути / (кол-во остановок я могу сделать+1), inf/(макс переход * расход)) * макс переход)
Работает очень быстро вот код:
http://codeforces.net/contest/1101/submission/48293038
Кто нибудь может сказать асимптотику такого решения?? буду благодарен =)!