A16531 | $Wishing Cards$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

据说在除夕夜写下心愿卡能带来好运。你已经写好了心愿卡，打算送给 Little A。 你邀请了 $n$ 位朋友帮你送心愿卡。你计划让第 $i$ 位朋友带 $b_i$ 张心愿卡。朋友们将依次以 $1$ 到 $n$ 的顺序拜访 Little A，每个人会把自己全部的 $b_i$ 张心愿卡交给 Little A。Little A 会记住送她心愿卡最多的那位朋友，所以在第 $j$ 位朋友拜访之后，她会获得等于当前收到的最多卡片数量的幸福值，即 $\max(b_1, b_2, \ldots, b_j)$。 第 $i$ 位朋友最多能携带 $a_i$ 张卡片，并且总共送出的卡片数不能超过 $k$。你的任务是在以上约束下，最优地选择每个人带卡片的数量 $b_i$，使得 $n$ 次拜访后 Little A 获得的总幸福值最大。 注意，有些朋友可以一张卡片也不带，Little A 并不会因此生气。

每组测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^3$）。接下来是每组测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^5$，$1 \le k \le 360$），分别表示朋友的数量和最大能送出的心愿卡总数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le k$），分别表示每个朋友最多能携带的卡片数。 保证所有测试用例中的 $n$ 总和不超过 $5 \times 10^5$，所有测试用例中的 $k$ 总和不超过 $1800$。

对于每个测试用例，输出 Little A 能获得的最大幸福值。

输入 #1

4
3 4
0 0 1
6 8
1 2 0 5 1 8
3 4
1 0 4
5 8
2 4 5 4 3

输出 #1

C++ 编辑器

输入

输出