No.1433 Two color sequence
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 219
作問者 : tyawanmusi / テスター : noya2
タグ : / 解いたユーザー数 219
作問者 : tyawanmusi / テスター : noya2
問題文最終更新日: 2021-03-20 00:19:30
問題文
長さ $N$ の整数列 $a=\{a_1,a_2,\dots,a_N\}$ が与えられます。整数列のそれぞれの要素は赤色か青色に塗られています。
この数列のある空でない連続部分列 $b$ のスコアを次のように定義します。
- $b$ に含まれる赤色に塗られた要素の総和を $R$ 、青色に塗られた要素の総和を $B$ として、スコアは $|R-B|$
- ただし、赤色に塗られた要素が存在しないとき、$R=0$
- 同様に、青色に塗られた要素が存在しないとき、$B=0$
スコアの最大値を求めてください。
制約
- $N,a_i$ は整数
- $1 \le N \le 2 \times 10^5$
- $-10^9 \le a_i \le 10^9$
入力
$N$ $S$ $a_1\ \ a_2\ \ \dots\ \ a_N$
$1$ 行目には整数 $N$ が、$2$ 行目には文字列 $S$ が、$3$ 行目には整数列 $a$ が空白区切りで入力されます。
ここで、$S$ は R
,B
からなる長さ $N$ の文字列です。$S$ の $i$ 文字目が R
なら $a_i$ は赤色に塗られています。$S$ の $i$ 文字目が B
なら $a_i$ は青色に塗られています。
出力
スコアの最大値を $1$ 行に出力してください。 最後に改行してください。
サンプル
サンプル1
入力
5 RRBBR 5 -6 1 2 3
出力
9
$a_1,a_2,a_5$ は赤色に、$a_3,a_4$ は青色に塗られています。
連続部分列 $\{a_1,a_2,a_3,a_4\}$ のスコアは $R=a_1+a_2=-1\ ,\ B=a_3+a_4=3$ より、$|R-B|=|-1-3|=4$ です。
連続部分列 $\{a_2,a_3,a_4\}$ のスコアは $R=a_2=-6\ ,\ B=a_3+a_4=3$ より、$|R-B|=|-6-3|=9$ です。
スコアの最大値は $9$ です。
サンプル2
入力
3 RRR 10 10 10
出力
30
サンプル3
入力
10 RRBBRBBRBR 6 -7 0 -8 -1 2 -6 4 9 -1
出力
15
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。