No.1433 Two color sequence
タグ : / 解いたユーザー数 222
作問者 :
tyawanmusi
/ テスター :
noya2
Problem Statement
You are given an integer sequence $a=\{a_1,a_2,\dots,a_N\}$ of length $N$. Each element of the sequence is painted either red or blue.
The score of a non-empty contiguous subarray $b$ of this sequence is defined as follows.
- Let $R$ be the sum of the elements painted red and $B$ be the sum of the elements painted blue among those contained in $b$. The score is $|R-B|$.
- However, if there are no elements painted red, $R=0$.
- Similarly, if there are no elements painted blue, $B=0$.
Find the maximum score.
Constraints
- $N,a_i$ are integers
- $1 \le N \le 2 \times 10^5$
- $-10^9 \le a_i \le 10^9$
Input
$N$ $S$ $a_1\ \ a_2\ \ \dots\ \ a_N$
Line $1$ contains the integer $N$, line $2$ contains the string $S$, and line $3$ contains the integer sequence $a$, separated by spaces.
Here, $S$ is a string of length $N$ consisting of R,B. If the $i$-th character of $S$ is R, then $a_i$ is painted red. If the $i$-th character of $S$ is B, then $a_i$ is painted blue.
Output
Print the maximum score on $1$ line. End the output with a newline.
Sample
Sample 1
Input
5 RRBBR 5 -6 1 2 3
Output
9
$a_1,a_2,a_5$ are painted red, and $a_3,a_4$ are painted blue.
The score of the contiguous subarray $\{a_1,a_2,a_3,a_4\}$ is $|R-B|=|-1-3|=4$, since $R=a_1+a_2=-1\ ,\ B=a_3+a_4=3$.
The score of the contiguous subarray $\{a_2,a_3,a_4\}$ is $|R-B|=|-6-3|=9$, since $R=a_2=-6\ ,\ B=a_3+a_4=3$.
The maximum score is $9$.
Sample 2
Input
3 RRR 10 10 10
Output
30
Sample 3
Input
10 RRBBRBBRBR 6 -7 0 -8 -1 2 -6 4 9 -1
Output
15
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。