← 返回比赛

已结束 GESP欢乐赛 #15

← 上一题下一题 →

A1556 | $接力长跑$

来源官方 / 2023

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

Yuilice最近跟小伙伴组建了Yuilice小队，准备去参与ACGO社区的接力长跑运动会。 接力长跑运动会在开始的时候，会给予每一位选手能力值$a_i(-10^3 \leq a_i \leq 10^3)$，并且规则如下: - 运动会过程当中，每当$i$位选手与$i+1$位选手接力成功时，该队分数会累加上与$a_{i+1}$能力值相同的分数，如果接力失败，分数则会清零。 - 只有能力值互为奇偶数的选手才可以成功接力，也就是$a_i$ % 2 != $a_{i+1}$ % 2。 - 每位选手可以自由选择是否接力，即使互为奇偶数也可以拒绝接力，自己起跑。(累加分数依然会清零，但是起跑选手的能力值会算入新的一轮累加分数中) - 最后得分为接力过程中，出现过的分数当中得分最高的分数。 现在给出Yuilice小队的每位成员的能力值$a_i$，并且必须按照给出的顺序进行长跑，请问Yuilice最多可以拿到多少得分？(注意，第一位起跑选手的分数也会被累加哦~)

输入格式

第一行输入一个整数$T$，代表接下来有$T(1 \leq T \leq 10^4 )$组样例进行计算。 每一组样例的第一行输入一个整数$n(1 \leq n \leq 2 · 10^5)$，代表小队共有$n$位成员。 随后一行，输入$n$个正整数$a_i(-10^3 \leq a_i \leq 10^3)$ 代表小队当中的每一位成员的能力值。

输出格式

输出一个整数，代表Yuilice能够得到的最高得分。

输入输出样例

输入 #1

7
5
5 4 3 2 1
10
7 8 9 11 2 3 4 5 2 1
4
-10 10 -5 10
3
4 -1 2
1
-10
3
1 1 1
2
4 4

输出 #1

C++ 编辑器

输入

输出