1034: 鼠鼠我鸭

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:758 Solved:357

Description

在一个叫做酱西功爷枝叶鸡树学院的地方有$n$只小动物,要么是鼠鼠,要么是鸭鸭,从$1$到$n$编号,每只小动物有个体重$a_i$。 在这个学校里,存在一种神奇的魔法,可以将编号位于某个区间$[l, r]$内的所有鼠鼠都变为鸭鸭,鸭鸭都变为鼠鼠(魔法并不会改变体重)。 现在你可以施放这个魔法至多$1$次。(也可以不施放) 问最终鸭鸭的总重量最多是多少? ### 输入格式 第一行一个整数$T$表示样例个数。$(1\le T \le 10)$ 对于每个样例: 第一行一个整数$n$表示小动物的个数。$(1\le n \le 10^5)$ 第二行$n$个整数,表示第$i$个小动物的类型。$0$表示鼠鼠,$1$表示鸭鸭。 第三行$n$个整数,表示第$i$个小动物的体重$a_i$。$(1 \le a_i \le 10^9)$ ### 输出格式 对于每个样例一行一个整数表示答案。 ### 样例输入1 ``` 2 3 0 0 0 1 2 3 4 0 1 0 0 2 5 6 5 ``` ### 样例输出1 ``` 6 16 ``` 解释:第二个样例中,翻转区间$[3, 4]$,使得结果最大为$5 + 6 + 5 = 16$。