시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 48 | 20 | 13 | 43.333% |
Lewin and Gan have a parentheses sequence. Nah, that word is clumsy as hell. Okay, one more time:
You are given a bracket sequence. Each bracket has one of 3 colors: lime, gray and blue and is either opening or closing.
You are allowed to change some brackets from opening to closing and vice versa. You are not allowed to change the order or colors of brackets. You want to do zero or more changes such that the resulting sequence satisfies the following:
A bracket sequence $S$ is balanced if it satisfies one of the following conditions:
Is it possible to do so and if it is, what is the minimum number of changes you have to make?
The first line contains a single integer $n$ ($1 \leq n \leq 6000$), the length of the bracket sequence.
The second line contains a string $s$ of length $n$ consisting of characters "(
" and ")
", the bracket sequence.
The third line contains $n$ integers $c_i$ ($0 \leq c_i \leq 2$). $c_i$ denotes the color of the $i$-th bracket. $0$ corresponds to lime, $1$ to gray and $2$ to blue.
Print a single integer --- the minimum number of changes you have to make if it is possible to satisfy the conditions and -1
otherwise.
5 ))))( 0 1 2 2 2
4
3 ()( 0 2 1
-1
6 (()()) 0 0 0 0 0 0
0
In the first example a possible resulting sequence is (()()
.