Good Bye 2018 |
---|
Закончено |
Боб — утка. Он хочет попасть в гнездо Алисы, чтобы пойти с ней вместе понырять.
Путешествие Боба может быть представлено в виде прямой линии, состоящей из $$$n$$$ отрезков. Боб находится слева от первого отрезка, а гнездо Алисы — справа от последнего отрезка. Длина каждого отрезка дана в метрах. Каждый отрезок имеет один из трех типов: трава, вода или лава.
Боб может передвигаться тремя способами: плаванием, ходьбой и полетом. Он может переключаться между ними или менять свое направление в любой момент времени (даже если он находится в нецелой координате), и для этого не требуется дополнительное время. Боб может плавать только по воде, ходить только по траве и летать над любой местностью. Чтобы пролететь один метр, нужна $$$1$$$ секунда. Чтобы проплыть один метр, нужно $$$3$$$ секунды. И, чтобы пройти один метр, нужно $$$5$$$ секунд.
У Боба конечное количество энергии. Плавание и ходьба расслабляют его, поэтому его количество энергии увеличивается на $$$1$$$ за каждый метр, который он проходит или проплывает. С другой стороны, летать довольно утомительно, поэтому его количество энергии уменьшается на $$$1$$$ за каждый метр полета. Пребывание на месте никак не влияет на его энергию. Конечно, количество энергии никогда не может становиться отрицательным. В начале количество энергии равно нулю.
За какое минимальное время Боб может достичь гнезда Алисы?
Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество отрезков.
Вторая строка содержит $$$n$$$ целых чисел $$$l_1, l_2, \dots, l_n$$$ ($$$1 \leq l_i \leq 10^{12}$$$), где $$$l_i$$$ — длина $$$i$$$-го отрезка в метрах.
Третья строка содержит строку $$$s$$$, состоящую из $$$n$$$ символов «G», «W», «L», которые обозначают траву (Grass), воду (Water) и лаву (Lava), соответственно.
Гарантируется, что первый отрезок не лава.
Выведите одно целое число $$$t$$$ — минимальное количество времени, которое нужно Бобу, чтобы добраться до гнезда Алисы.
1 10 G
30
2 10 10 WL
40
2 1 2 WL
8
3 10 10 10 GLW
80
В первом примере Боб сначала проходит $$$5$$$ метров за $$$25$$$ секунд. После этого он пролетает оставшиеся $$$5$$$ метров за $$$5$$$ секунд.
Во втором примере Боб сначала проплывает $$$10$$$ метров за $$$30$$$ секунд. После этого он пролетает над лавой за $$$10$$$ секунд.
В третьем примере водный пруд намного меньше. Боб сначала проплывает по нему за $$$3$$$ секунды. Однако он пока что не может пролететь над лавой, так как у него только одна единица энергии, а ему нужно две. Поэтому он проплывет полметра назад, а потом вернется вперед. Это займет $$$3$$$ секунды. Теперь у него есть $$$2$$$ единицы энергии, значит он сможет пролететь лаву за $$$2$$$ секунды.
В четвертом примере он будет ходить $$$50$$$ секунд, летать $$$10$$$ секунд, плавать $$$15$$$ секунд и в конце летать $$$5$$$ секунд.
Название |
---|