A16819 | $Odd Process$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

你有 $n$ 枚硬币，面额分别为 $a_1, a_2, \ldots, a_n$，还有一个自然数 $k$。你有一个最开始为空的包，你可以把硬币放进去。你需要恰好进行 $k$ 次操作，每次操作选一个剩下的硬币放进包里，该硬币之后不能再选。 同时，你有一只非常喜欢偶数的猫，每当你包内硬币的面额和变为偶数时，猫就会把包清空，也就是它把包里所有硬币都带走了，包会变为空。注意，只要放了一个硬币后包内的和变为偶数，无论在什么时候，猫都会立刻把包清空，不仅仅是在最后一步。 记你的得分为包中硬币面额的和。你的任务是，用 $k$ 次操作让最终分数最大。请你计算所有 $1 \leq k \leq n$ 时的最大可能最终分数，并输出。

每个测试包含多组数据。第一行为测试组数 $t$（$1 \leq t \leq 10^4$）。 每组数据的第一行包含一个正整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示硬币数量。 每组数据的第二行包含 $n$ 个自然数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示硬币的面额。 保证所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组数据，输出 $n$ 个数，第 $k$ 个数表示恰好进行 $k$ 次操作后的最大可能得分。每组输出占一行。

输入 #1

输出 #1

C++ 编辑器

输入

输出