Входной файл: | mail.in | Ограничение времени: | 4 сек | |
Выходной файл: | mail.out | Ограничение памяти: | 256 Мб |
В Флатландии идет пора реформ. Недавно была проведена реформа дорог, так что теперь по дорогам страны из любого города можно добраться в любой другой, причем только одним способом. Также была проведена реформа волшебников, так что в каждом городе остался ровно один волшебник. Теперь же началась реформа почтовой системы.
Недавно образованное почтовое агентство "Экс-Федя" предлагает уникальную услугу — коллективную посылку. Эта услуга позволяет отправлять посылки жителям всех городов на каком-либо пути по цене обычной посылки. Удивительно, но пользоваться такой услугой стали только волшебники Флатландии, которые стали в большом количестве отправлять друг другу магические кактусы. Агентство столкнулось с непредвиденной проблемой: как известно, все волшебники живут в башнях и мало того, что не строят в них лестницы, так еще время от времени меняют их высоту. Поэтому, чтобы доставить посылку волшебнику, который живет в башне высотой h, курьеру агентства требуется иметь с собой не менее h метров веревки.
Вам поручено руководить отделом логистики — по имеющимся данным о высотах башен и об их изменениях вам нужно определять минимальную длину веревки, которую нужно выдать курьеру, который доставляет посылки между городами i и j.
!
i h,
1 ≤ i ≤ n, 1 ≤ h ≤ 105. ?
i j, 1 ≤ i, j ≤ n.
№ | Входной файл (mail.in ) |
Выходной файл (mail.out ) |
---|---|---|
1 |
|
|
2 |
|
|