传统题 1000ms 256MiB

背包问题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

神奇商店中一共有 NN 种不同的物品,第 ii 种物品的重量为 WiW_i​,每种物品的数量都是无限个。店主会从中挑选任意种商品,每种商品可以选择任意个并将其装入到一个背包之中,从而可以组合出多种背包(这个背包可以容纳无限多的物品),其中背包的重量就是其中所含物品的重量之和。小蓝想要的背包中至少要有 KK 件物品。小蓝想要知道,在所有满足他要求的背包中,如果将背包重量从小到大排序并去除重复的重量,排名第 LL 的重量是多少。

输入格式

第一行输入三个整数,用空格分隔,依次是 NNKKLL。 第二行输入 NN 个用空格分隔的整数表示 NN 件物品的重量。

输出格式

输出一行,包含一个整数表示答案。

7 2 7
84 21 12 3 65 5 41
13

样例说明

背包中物品个数大于等于 22 时,从小到大依次出现的背包重量为:

  • 6=3+36=3+3
  • 8=3+58=3+5
  • 9=3+3+39=3+3+3
  • 10=5+510=5+5
  • 11=3+3+511=3+3+5
  • 12=3+3+3+312=3+3+3+3
  • 13=3+5+513=3+5+5
  • 所以答案为 13

评测用例规模与约定

对于 40%40\% 的评测用例:1Wi1001≤W_i≤1001L101≤L≤10

对于 100%100\% 的评测用例:1N101≤N≤101K101≤K≤101Wi1091≤W_i≤10^91L1051≤L≤10^5

训练赛六

未参加
状态
已结束
规则
乐多
题目
11
开始于
2025-6-5 13:00
结束于
2025-6-5 17:00
持续时间
4 小时
主持人
参赛人数
8