問題一覧 > 通常問題

No.3148 Min-Cost Destruction of Parentheses

レベル : / AI推定難易度 : 2575 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 26
作問者 : nauclhlt / テスター : naniwazu 👑 p-adic
お気に入りにしたユーザー ProblemId : 12135 / 自分の提出
問題文最終更新日: 2025-05-15 18:23:43
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 (順位表) の他の問題:

Problem Statement

Definition of a balanced parenthesis sequence

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

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

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


There is a balanced parenthesis sequence $S$ of length $2N$. Initially, $S$ contains exactly $N$ occurrences of (; we call these opening brackets $1, 2, \cdots, N$ from left to right.

Also, the ) corresponding to opening bracket $i$ is called closing bracket $i$, and the pair of opening bracket $i$ and closing bracket $i$ is called pair $i$. Here, "corresponding" means being deleted at the same time in the definition of a balanced parenthesis sequence.

Note that the numbers assigned to the brackets do not change even when $S$ is modified. For example, even if pair $2$ is deleted, pair $3$ does not newly become pair $2$.

There is a sequence of non-negative integers $A=(A_1, A_2, \cdots, A_N)$ of length $N$, and initially $x=0$. nauclhlt will now repeat the following operation until $S$ becomes the empty string.

  • Choose one () contained in $S$ as a substring and delete it. If the chosen () is pair $k$, add $A_k$ to $x$. After that, a cost of $x$ is incurred

Find the minimum possible total cost incurred by the end of the operations.

Input

$N$
$S$
$A_1\ A_2\ \cdots\ A_N$
  • $1\leq N\leq 10^5$
  • $S$ is a balanced parenthesis sequence of length $2N$
  • $0\leq A_i\leq 500$
  • $N, A_i$ are integers

Output

Let $m$ be the minimum total cost. Output it on $1$ line in the following format.

$m$

Print a newline at the end.

Sample

Sample 1
Input
3
()(())
2 5 1
Output
12

A total cost of $12$ can be achieved as follows.

  • In the 1st operation, choose the () that is pair $3$. Now $x=1$, and a cost of $1$ is incurred
  • In the 2nd operation, choose the () that is pair $1$. Now $x=3$, and a cost of $3$ is incurred
  • In the 3rd operation, choose the () that is pair $2$. Now $x=8$, and a cost of $8$ is incurred

It is impossible to finish the operations with a total cost less than $12$, so the answer is 12.

Sample 2
Input
4
()()()()
1 1 1 1
Output
10
Sample 3
Input
3
()(())
1 0 1
Output
4

A total cost of $4$ can be achieved as follows, and this is the minimum.

  • In the 1st operation, choose the () that is pair $3$. Now $x=1$, and a cost of $1$ is incurred
  • In the 2nd operation, choose the () that is pair $2$. Now $x=1$, and a cost of $1$ is incurred
  • In the 3rd operation, choose the () that is pair $1$. Now $x=2$, and a cost of $2$ is incurred

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