0056. OH!
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Ограничение по времени: | 1 s |
| Ограничение по памяти: | 64 megabytes |
На первом этаже Всемирного торгового центра в момент атаки самолёта, управляемого исламским фундаменталистом Запоем Маглоевым, находится Чапаев, который мечтает лишить здание спиртного, пока сотрудники спускаются по внешним пожарным лестницам. Он может передвигаться на лифте, который двигается со скоростью K этажей в минуту. Пожар распространяется со скоростью L этажей в минуту, но не быстрее лифта. На то, чтобы выпить весь спирт на этаже, Василию Ивановичу надо M минут (вне зависимости от количества спирта). Если лифт проезжает через горящий этаж, или пожар приходит на тот этаж, на котором находится лифт √ лифт застревает и Василий Иванович вынужден избавиться от всего выпитого естественным путём. Василию Ивановичу заранее известно, сколько спирта на каждом этаже, а также номер нижнего этажа, охваченного пожаром √ P. Определите максимальное число выпитого Василием Ивановичем спирта.
Формат входного файла
В первой строке записаны натуральные числа P,K,L,M ≤ 1024, N ≤ 100000, P ≤ 512. В последующих N-1 строках содержатся числа √ количество бутылок спирта на каждом этаже, начиная со второго до последнего. Спирта на этаже не более 65536.
Формат выходного файла
В выходном файле должно быть число √ максимальное количество спирта, которое выпьет Василий Иванович.
Пример:
| input.txt | output.txt |
|---|---|
| 5 1 1 1 5 100 100 100 100 | 100 |
Clarification1: Если огонь приходит на этаж в тот момент, когда лифт уезжает, лифт застревает. Лифт должен иметь запас времени по сравнению с огнем.
Clarification2: Василий Иванович всегда допивает весь спирт на этаже до конца!
Источник: Petrozavodsk training camp, Summer 2002. Magloy's contest :-)
Автор: Magloy (Alexander Korol, Denis Vlasov, Roman Soshkin)
Обсудить Отправить решение