問題一覧 > 通常問題

No.3147 Parentheses Modification and Rotation (RM Ver.)

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 48
作問者 : nauclhlt / テスター : naniwazu
お気に入りにしたユーザー ProblemId : 12277 / 自分の提出
問題文最終更新日: 2025-05-16 22:54:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 467 (順位表) の他の問題:

Note

This problem has almost the same setting as E. Only the constraints on $R, M$ differ.

You can get AC on E by submitting a solution to this problem as is.

Problem Statement

Definition of a balanced parenthesis sequence

A string $X$ is a balanced parenthesis sequence if the following holds.

  • $X$ can be made into the empty string by repeating, $0$ or more times, the operation of deleting a () contained in $X$ as a contiguous substring

For example, ()(()) and ()()()() are balanced parenthesis sequences, but ))(( and )()()( are not balanced parenthesis sequences.


There is a string $S$ of length $N$. Here, $S$ consists of ( and ).

nauclhlt wants to make $S$ a balanced parenthesis sequence by repeating the following operation $0$ or more times.

Operation

  • Choose either a type $1$ or a type $2$ operation and perform it $1$ time.
    • Type $1$: Rotate $S$ to the right. Formally, replace $S$ with the string obtained by concatenating, in this order, the $N$-th character of $S$ and the string formed by taking the $1$-st through $N-1$-th characters of $S$. This operation costs $R$.
    • Type $2$: Choose an integer $i$ satisfying $1\leq i\leq N$ and a character $c\in \lbrace $ ( $,$ ) $\rbrace$, and replace the $i$-th character of $S$ with $c$. This operation costs $M$.

Determine whether nauclhlt can make $S$ a balanced parenthesis sequence through operations, and if possible, find the minimum possible total cost.

Input

$N$
$S$
$R$ $M$
  • $1\leq N\leq 10^5$
  • $0\leq R, M\leq 10^7$
  • $S$ is a string of length $N$ consisting of ( and )
  • $N, R, M$ are integers

Output

If $S$ can be made into a balanced parenthesis sequence, let $m$ be the minimum total cost and print it on $1$ line in the following format.

$m$

If it is impossible, print -1.

$-1$

Print a newline at the end.

Sample

Sample 1
Input
6
)()()(
1 1
Output
1

For example, the following operation makes $S$ a balanced parenthesis sequence with a total cost of $1$.

  • Perform a type $1$ operation. It costs $1$, and $S$ becomes ()()()

Note that there may be multiple sequences of operations that achieve the optimal solution.

Sample 2
Input
4
)))(
1000 1
Output
3

Example of a sequence of operations:

  • Choose $i=1, c=$( and perform a type $2$ operation. It costs $1$, and $S$ becomes ())(
  • Choose $i=3, c=$( and perform a type $2$ operation. It costs $1$, and $S$ becomes ()((
  • Choose $i=4, c=$) and perform a type $2$ operation. It costs $1$, and $S$ becomes ()()

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。