Оптимайз nmlogn к задаче E Educational Codeforces Round 58

Revision ru1, by Jostic11, 2019-01-12 16:50:24

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

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

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

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

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

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

http://codeforces.net/contest/1101/submission/48293038

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

Tags educational 58, бп, оптимайз

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru7 Russian Jostic11 2019-01-12 23:31:40 8
ru6 Russian Jostic11 2019-01-12 17:03:06 28
ru5 Russian Jostic11 2019-01-12 16:54:12 2
ru4 Russian Jostic11 2019-01-12 16:52:30 28 Мелкая правка: 'заметил =(\n\n\nr = ' -> 'заметил =( для AC надо писать вот так:\n\n\nr = '
ru3 Russian Jostic11 2019-01-12 16:51:49 8 Мелкая правка: 'и+1)+1);\nansw — максимум ' -> 'и+1)+1);\n\n\nansw - это максимум '
ru2 Russian Jostic11 2019-01-12 16:51:02 7 Мелкая правка: 'привет =) Пока у меня (над' -> 'привет =) У меня (над'
ru1 Russian Jostic11 2019-01-12 16:50:24 892 Первая редакция (опубликовано)