CF632B Alice, Bob, Two Teams

Alice 和 Bob 正在玩一个游戏。该游戏涉及将游戏棋子分成两队。有 $n$ 个棋子，第 $i$ 个棋子有一个强度 $p_{i}$。 分组的方式如下： 1. 首先，Alice 会将这些棋子分成两个不同的小组 $A$ 和 $B$。这可以表示为一个长度为 $n$ 的字符串，其中每个字符是 $A$ 或 $B$，表示该棋子分配到哪个组。 2. 接着，Bob 可以任选该字符串的一个前缀或后缀，并且翻转该前缀或后缀中的每个字符（即将 $A$ 变为 $B$，将 $B$ 变为 $A$）。这一操作最多只能进行一次（也可以选择什么都不做）。 3. 最终，Alice 得到所有标记为 $A$ 的棋子，Bob 得到所有标记为 $B$ 的棋子。 一名玩家的强度为其所分到的所有棋子的强度之和。 现在给定 Alice 初始的分组方案，请帮助 Bob 决定最优策略，使他能获得最大的强度，并输出 Bob 能获得的最大强度。

第一行包含一个整数 $n$（$1\le n \le 5\times 10^{5}$）——表示棋子的数量。 第二行包含 $n$ 个整数 $p_{i}$（$1\le p_{i} \le 10^{9}$）——第 $i$ 个棋子的强度。 第三行包含一个长度为 $n$ 的仅由 $A$ 和 $B$ 组成的字符串——表示 Alice 分配后的分组情况。

输出一个整数 $a$——表示 Bob 能获得的最大强度。

在第一个样例中，Bob 应该翻转长度为 $1$ 的后缀。 在第二个样例中，Bob 应该翻转长度为 $5$ 的前缀或后缀（两者相同）。 在第三个样例中，Bob 什么都不用做。 由 ChatGPT 5 翻译