eolymp
bolt
Try our new interface for solving problems
Məsələlər

Перефарбуйте кульку

Перефарбуйте кульку

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

У Сема i Юри є n кульок, кожна кулька або чорна, або бiла. Також кожна кулька має свою цiннiсть c[i] та максимальну кiлькiсть разiв, скiльки її можна перефарбовувати, a.Тепер же Сем i Юра вирiшили зiграти у гру. За один хiд гравець може перефарбувати кульку в чорний або бiлий колiр або пропустити хiд. Одну кульку не можна перефарбовувати бiльше, нiж a[i] разiв. Можна перефарбовувати кульку в той же колiр, в який вона зараз пофарбована. Сем ходить першим. Гра закiнчується, коли жодну кульку вже неможливо перефарбувати або обидва гравцi пiдряд пропустили хiд.

Пiсля цього Сем забирає собi всi бiлi кульки, а Юра всi чорнi. Результат кожного з гравцiв — сума цiнностей його кульок. Обидва гравцi хочуть максимiзувати свiй результат. Знайдiть, який буде кiнцевий результат, якщо обидва гравцi грають оптимально.

Giriş verilənləri

Перший рядок мiстить одне цiле число n (1 ⩽ n ⩽ 10^5) — кiлькiсть кульок.

Другий рядок мiстить n цiлих чисел c[1]; c[2]; : : : ; c[n] (1 ⩽ c[i]10^9) — цiннiсть i-ої кульки.

Третiй рядок мiстить n цiлих чисел a[1]; a[2]; : : : ; a[n] (1 ⩽ a[i]10^9) — максимальна кiлькiсть разiв, скiльки можна перефарбувати i-ту кiльку.Четвертий рядок мiстить n символiв «W» та «B». i-ий символ рiвний «W», якщо i-та кулька спочатку бiлого кольору, i «B», якщо чорного.

Çıxış verilənləri

Виведiть два цiлi числа — результати Сема i Юри вiдповiдно

Nümunə

Giriş verilənləri #1
4
47 7 17 1
2 3 5 4
WBBW
Çıxış verilənləri #1
65 7
Mənbə 2019-2020 ACM-ICPC, SEERC, 1/8 фiналу, 13 квiтня 2019 року