ヒント：https://atcoder.jp/contests/arc211/editorial/14503

両端の木はないものとしてよいですから、以降は両端には木がないものとします。

まず、消す木はちょうど \(1\) つの区間をなすものとしてよいです。\(2\) つ以上の区間の木を一度に消すなら、\(1\) つずつ消すようにすることで報酬を真に増やすことができます。

初期状態の木のある区間の数を \(n\) 、木のない区間の \(R\) の最大値を順に並べたものを \((r_1,r_2,\dots,r_{n+1})\) とします。報酬に関わる \(R\) の要素は重複も含めて \(2n\) 個で、そのうち \(n+1\) 個は \(r\) に含まれているものです。残りの \(n-1\) 個をすべて \(R\) の最大値にすることができれば、それは報酬の上界です。これは達成可能でしょうか？

最初の操作で \(R\) の最大値に関わる箇所（その間の木が消えることで \(R\) の最大値の区画で操作できるようになる箇所も含みます）を選ぶと、以降そこにある \(R\) の最大値と \(r\) に含まれるものを適切に組み合わせて操作すれば、上界を達成することが可能です。逆に、\(R\) の最大値に関わらない場所を操作してしまうと、類似の議論により上界が達成不可能になることがわかります。

よって、\(R\) の最大値に関わる場所すべてについて、そこに操作する通り数を求め、すべて足し合わせればよいです。事前に木の有無でランレングス圧縮することでこれは \(O(N)\) の時間計算量で可能です。よって、この問題を解くことができました。

実装のポイントです。両端に木のある区画を付け足すことで、場合分けを減らすことができます。

とるべき最大値は（素の状態の）\(R\) の最大値ではなく、両端から木のある区画を取り除いたときの \(R\) の最大値であることに注意してください。

答えは32bit整数の範囲内に収まらない場合があるので、C++等の通常32bit整数を使う言語の場合は注意してください。

実装例 (Python (Codon 0.19.3), 39ms)

N = int(input()) + 2
S = "#" + input() + "#"
R = [0] + list(map(int, input().split())) + [0]

now = "#"
mx = 0
cnt = 0
rle = []

for i in range(N):
    if S[i] == now:
        if mx == R[i]:
            cnt += 1
        elif mx < R[i]:
            mx = R[i]
            cnt = 1
    else:
        rle.append((mx, cnt))
        now = S[i]
        mx = R[i]
        cnt = 1

rle = rle[1:]
mx = max(rle)[0]
ans = 0

for i in range(0, len(rle) - 1, 2):
    if max(rle[i][0], rle[i + 1][0], rle[i + 2][0]) == mx:
        ans += rle[i][1] * rle[i + 2][1]

print(ans)