루미 알고리즘

#1644플래티넘The Cat Necklace

PO 2026 훈련 캠프코딩출제 Harry Zhang, Nils Gustafsson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

Lulli, The Cat

Louise loves her cat Lulli very much and therefore plants lots of catnip.

Now Louise wants to create a beautiful necklace for Lulli with N charms placed in a ring. On each charm there is exactly one symbol, either ( or ). The necklace also has a bell that marks where to start reading.

To make the necklace extra beautiful, Louise wants the necklace to be balanced. For help, Louise hires a jeweler who can modify the necklace. As payment, she uses catmints.

The jeweler can remove any charm for a cost of a catmints per charm. The jeweler can also rotate the necklace one step, so that the first charm moves to the end, which costs b catmints. Louise is also satisfied if the necklace becomes completely empty, but then she must pay to remove each charm.

Louise therefore wants to make the necklace balanced at the lowest possible cost.

A necklace is balanced if its symbols, read in order from the bell, form a balanced parenthesis string. A parenthesis string is balanced if:

  • It is empty, or
  • It can be written as AB, where both A and B are balanced strings, or
  • It can be written as (A), where A is a balanced string.

Input

The first line contains three integers N, a and b (1 ≤ N ≤ 5 · 10^5, 0 ≤ a,b ≤ 10^9).

The second line contains a string s of length N. Each symbol in s is either ( or ).

Output

Print one integer: the minimum possible total cost to make the necklace balanced.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

GroupPointsConstraints
111a = 1, b = 10^9
216N ≤ 15
319N ≤ 100
421N ≤ 2000
59b = 0
68a = 10^9, b = 1, there are equally many ( as ) in the input string.
716No additional constraints.

Explanation of Samples

In sample 1, you can first rotate the necklace two steps.

(그림은 원문 저장소에서 볼 수 있습니다)

Then the necklace reads as )(()).

(그림은 원문 저장소에서 볼 수 있습니다)

If you then remove the first charm, which is ), the necklace reads as (()), which is balanced.

(그림은 원문 저장소에서 볼 수 있습니다)

The total cost is 3 + 3 + 2 = 8 catmints.

In sample 2, you can remove the second charm, which is ), and then the last charm, which is (. Then the necklace reads as ()()(), which is balanced. The total cost is 4 + 4 = 8 catmints.

In sample 3, you can rotate the necklace three steps, so that the necklace reads as ()()(()). It is already balanced, so the total cost is 3 + 3 + 3 = 9 catmints.

예제

예제 1

입력
5 2 3
)))((
출력
8

예제 2

입력
8 4 3
())()()(
출력
8

예제 3

입력
8 5 3
())()()(
출력
9

출처 표기

출처: Programmeringsolympiaden 2026년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.