E. 脸盆大哥(buhsi)

    Type: Default 1000ms 256MiB

脸盆大哥(buhsi)

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

彩虹岛的木桶

时间限制:C/C++/Rust/Pascal 1秒,其他语言 2秒
空间限制:C/C++/Rust/Pascal 128M,其他语言 256M
64bit IO 格式:%lld

题目描述

彩虹岛网红脸盆大哥最骄傲的就是自己制作的木桶。一天,lwq 拿了 n 块木板,其中第 i 块木板的高度为 h_i。他希望脸盆大哥能够用这些木板制作出精美的木桶。

脸盆大哥告诉 lwq:

  • 制作一个木桶需要 k 块木板;
  • 所有桶的底面积固定为 s(底面的木板由 s 块木板组成,但不需要考虑具体组合方式,哪怕 1 块或 2 块木板也可以组成木桶,底面积仍为 s)。

lwq 想知道,用这些木板制作出来的木桶最多能够盛多少体积的水。

注意:木板不能重叠,且未使用的木板可以丢弃。

输入描述

第一行输入一个整数 T(2 ≤ T ≤ 20),表示共有 T 组测试数据。

对于每组测试数据:

  • 第一行输入三个整数 n, k, s(1 ≤ n, k, s ≤ 10^3),分别表示木板总数、每个木桶需要的木板数、木桶底面积。
  • 第二行输入 n 个整数 h_i(1 ≤ h_i ≤ 10^3),表示每块木板的高度。

输出描述

对于每组测试数据,输出一个整数 x,代表能装水的最大体积。

示例 1

2
4 2 5
1 2 3 4
5 2 5
1 4 5 2 3

text

20
30

说明

  • 第一组:第一个桶由高度 1、2 组成,盛水体积为 1×5=5;第二个桶由 3、4 组成,盛水体积为 3×5=15,总计 20。
  • 第二组:丢弃高度 1 的木板,剩余 (2,3) 和 (4,5) 组成两桶,最短板为 2 和 4,体积 = (2+4)×5 = 30。

校赛新手热身(二)

Not Attended
Status
Done
Rule
XCPC
Problem
7
Start at
2026-11-9 22:30
End at
2026-11-16 4:30
Duration
150 hour(s)
Host
Partic.
90