logo AlgoBeat OnlineJudge
登录 注册

#215920. 【MX-X26-T4】「Cfz Round 7」breakfast

内存限制:1024 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

醒めない夢も 情けない現実も / 醒不来的梦也罢 难堪的现实也罢

ただ景色になっていく / 终将化作寻常风景


Yuki 有一个长度为 的序列

对于序列 ,Yuki 定义其「鱼鱼值」等于:

即序列 的所有非空前缀的 之和。

Yuki 定义一次「大了」操作为:

  • 选择一个不大于 的正整数 和一个非负整数 ,将 的值修改为

你需要对于每个不大于 的非负整数 求出,若 Yuki 进行恰好 次「大了」操作,序列 的「鱼鱼值」最大能达到多少。

本题中,一个序列的 为该序列中未出现过的最小非负整数,例如:

特别地,当序列为空时,该序列的

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 ,分别表示该测试点所属的子任务编号和测试数据组数。样例满足

接下来依次输入每组测试数据。对于每组测试数据:

  • 第一行包含一个整数
  • 第二行包含 个整数

输出格式

对于每组测试数据,输出一行,包含 个整数;第 个整数表示,若 Yuki 进行恰好 次「大了」操作,序列 的「鱼鱼值」所能达到的最大值。

样例

样例输入 1

0 3
4
2 0 0 9
5
0 1 0 2 4
7
4 0 9 8 1 3 8

样例输出 1

3 7 7 7 7
11 14 15 15 15 15
9 9 9 9 9 9 9 9

数据范围与提示

样例 1 解释

对于第 组测试数据:

  • 时,序列 的「鱼鱼值」为
  • 时,可以将 的值修改为 ,此时序列 的「鱼鱼值」为

对于第 组测试数据:

  • 时,序列 的「鱼鱼值」为
  • 时,可以将 的值修改为 ,此时序列 的「鱼鱼值」为
  • 时,可以将 的值分别修改为 ,此时序列 的「鱼鱼值」为

数据范围

表示单个测试点中 的和, 表示单个测试点中 的和。

对于所有测试数据,均有:

  • 对于所有 ,均有

本题采用捆绑测试。

  • Subtask 1(13 points):
  • Subtask 2(17 points):
  • Subtask 3(27 points):
  • Subtask 4(7 points):保证序列 的排列。
  • Subtask 5(15 points):保证序列 单调不降。
  • Subtask 6(21 points):无特殊限制。