package main import . "fmt" import . "os" import bf "bufio" func main() { rd := bf.NewReader(Stdin) var n int var s string Fscan(rd,&n,&s) var dpMin, dpMax, ans int for i := 0; i < n; i++ { var a int Fscan(rd,&a) if s[i] == 'B' { a = -a } if i == 0 { dpMin = a dpMax = a ans = max(a, -a) } else { dpMin = min(dpMin+a, a) dpMax = max(dpMax+a, a) ans = max(ans, dpMin, -dpMin, dpMax, -dpMax) } } Println(ans) } /* 考察 RBの文字列のは特に意味はなさそう? Bに相当するA[i]の正負を反転させるだけのような 動的計画法ぽそう 2つの状態を持って A[i]のときに ・A[i-1]を含む連続部分列で最小の和 DPmin ・A[i-1]を含む連続部分列で最大の和 DPmax として DPmin = min(DPmin+A[i], A[i]) DPmax = max(DPmax+A[i], A[i]) answer = max(answer,abs(DPmax),abs(DPmin)) かなあ */