分数: 450 点
问题陈述
给你一个非负整数序列 A = (A_1,\dots,A_{2N}) 长度 2N.
定义括号序列的分数 s 长度 2N 如下:
- 对于每个位置 i 其中 i- 第一个字符 s is
),设置 A_i to 0,然后取所有元素的总和 A.
找到长度正确的括号序列的最大可能得分 2N.
你被给予 T 测试用例;逐一解决。
什么是正确的括号序列?
正确的括号序列是可以通过重复删除等于的子字符串来减少为空字符串的字符串().
约束
- 1 \le T \le 500
- 1 \le N \le 2 \times 10^{5}
- 对于每个输入文件,总和 N 所有测试用例最多 2 \times 10^{5}.
- 0 \le A_i \le 10^{9} (1 \le i \le 2N)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T
\textrm{case}_i 代表 i- 第一个测试用例。每个测试用例均按以下格式给出:
N
A_1
A_2
\vdots
A_{2N}
输出
输出 T 行。的 i- 第行 (1 \le i \le T)应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
2 3 400 500 200 100 300 600 6 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 1
1200 6000000000
在第一个测试用例中,选择正确的括号字符串 (())() 给出的分数为 400+500+0+0+300+0=1200.
没有正确的括号字符串会产生更高的分数,所以答案是 1200.
请注意,正如本示例的第二个测试用例一样,答案可能超出 32 位整数范围。