п»ї
\(N\) \((1 \leq N \leq 2 \cdot 10^5)\) коров Фермера Джона выстроены в круг
так, что для каждой коровы \(i\) в промежутке \(1,2,\dots,N-1\), справа от коровы
\(i\) расположена корова \(i+1\), а справа от коровы \(N\) находится корова \(1\).
У каждой коровы имеется ведро целочисленной ёмкостью \(a_i\)
\((1 \leq a_i \leq 10^9)\) литров. Все вёдра изначально заполнены молоком.
Каждую минуту коровы обменивается молоком по правилу, описанному в строке
\(s_1s_2\dots s_N\) , состоящей только из символов \(\text{�L’}\) и \(\text{�R’}\).
Если у коровы есть хотя бы \(1\) литр молока, она отдаст ровно \(1\) литр молока
корове слева от неё, если \(s_i=\text{�L’}\), или справа от неё, если
\(s_i=\text{�R’}\). Все обмены происходят одновременно (то есть, если у коровы
полное ведро и она отдаёт литр молока и получает литр молока, то её молоко
сохраняется). Если количество молока превысит \(a_i\), то лишнее молоко будет утеряно.
ФД хочет узнать после \(M\) минут \((1 \leq M \leq 10^9\)), какое количество
молока останется у всех коров.?
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) Рё
\(M\).
Вторая строка содержит строку \(s_1s_2\dots s_N\) состоящую только из
символов \(\text{�L’}\) или \(\text{�R’}\), обозначающих направление, в котором
каждая корова будет передавать своё молоко.
Третья строка содержит целые числа \(a_1, a_2, \dots, a_N\), ёмкости каждого
ведра.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите одно целое число, сумму молока всех коров после
\(M\) РјРёРЅСѓС‚.
Заметим, что требуется использовать 64-битный целый тип
(например, "long long" в C/C++).)
ПР�МЕРВВОДА:
3 1
RRL
1 1 1
ПР�МЕРВЫВОДА:
2
Коровы \(2\) и \(3\) передадут друг другу по 1 литру молока, поэтому их молоко сохранится.
Когда корова \(1\) передаст свой литр молока корове \(2\), ведро у той переполнится
и один литр молока будет потерян на 1-ой минуте.
ПР�МЕРВВОДА:
5 20
LLLLL
3 3 2 3 3
ПР�МЕРВЫВОДА:
14
Каждая корова передаёт литр молока и получает литр молока, поэтому всё молоко сохранится
вне зависимости от количества минут.
ПР�МЕРВВОДА:
9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4
ПР�МЕРВЫВОДА:
38
�значально имеется всего 51 литр молока. Через 5 минут
коровы \(3\), \(6\), \(7\) потеряют 5, 3, 5 литров соответственно.
Поэтому останется 38 литров молока.
ОЦЕН�ВАН�Е:
- Тесты 4-8: \(N,M \le 1000\)
- Тесты 9-16: Нет дополнительных ограничений.
Авторы: Chongtian Ma, Alex Liang