問題一覧 > 通常問題

No.1433 Two color sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 176
作問者 : tyawanmusityawanmusi / テスター : noya2noya2
14 ProblemId : 5542 / 出題時の順位表
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。