Задача - 926H - Codeforces

VK Cup 2018 - Уайлд-кард Раунд 1
Закончено

→ Виртуальное участие

Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований. Если вы раньше видели эти задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве. Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве. Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.

→ Особенности соревнования

Это раунд имеет необычное дополнение к правилам. Для каждой задачи вы должны использовать свой язык. Таким образом, если у вас есть попытка, которая прошла хотя бы один тест по задаче или тестируемая в настоящий момент, то для этой задачи вы можете использовать только этот язык и не можете использовать его для решения других задач. Подробнее можно прочитать по ссылке. Разные реализации одного языка считаются одинаковым языком (например, на C++ вы можете сдавать лишь одну задачу, независимо от выбранного компилятора).

→ Теги задачи

*2200

Нет прав на редактирование

Аркадий решил купить букет роз своей подруге.

В цветочном магазине есть белые, оранжевые и красные розы, причём их суммарное количество равно n. Аркадий считает, что красные розы с белыми не сочетаются, поэтому не будет покупать букет, содержащий и красные, и белые розы. Кроме того, Аркадий не будет покупать одноцветный букет.

Всего Аркадий хочет купить ровно k роз. Для каждой розы известна её красота и цвет: красота i-й розы равна b_i, а её цвет — c_i («W» для белой розы, «O» для оранжевой розы и «R» для красной розы).

Определите максимально возможную суммарную красоту букета из k роз, удовлетворяющего условиям выше, либо сообщите, что собрать такой букет из роз, имеющихся в магазине, невозможно.

Входные данные

В первой строке следуют два целых числа n и k (1 ≤ k ≤ n ≤ 200 000) — количество роз в магазине и количество роз, которые Аркадий хочет купить.

Во второй строке следует последовательность целых чисел b₁, b₂, ..., b_n (1 ≤ b_i ≤ 10 000), где b_i равно красоте i-й розы.

В третьей строке следует строка c длины n, состоящая из букв «W», «O» и «R», причем c_i соответствует цвету i-й розы: «W» — белая роза, «O» — оранжевая роза, «R» — красная роза.

Выходные данные

Выведите максимально возможную суммарную красоту букета из k роз, который удовлетворяет описанным условиям. Если невозможно собрать ни одного такого букета, выведите -1.

Примеры

Входные данные

5 3
4 3 4 1 6
RROWW

Выходные данные

Входные данные

5 2
10 20 14 20 11
RRRRR

Выходные данные

-1

Входные данные

11 5
5 6 3 2 3 4 7 5 4 5 6
RWOORWORROW

Выходные данные

Примечание

В первом примере Аркадий должен купить 3 розы. Он может, например, купить обе красные розы (их номера 1 и 2, а суммарная красота 7) и единственную оранжевую розу (её номер равен 3, а красота равна 4). Таким образом, суммарная красота букета будет равна 11.

Во втором примере Аркадий не сможет купить букет, так как все розы в магазине одноцветные.

Соревнования по программированию 2.0

Время на сервере: 19.04.2024 03:47:09 (j2).

Десктопная версия, переключиться на мобильную.

При поддержке