A4713 | $废品回收$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

时间限制：1000ms，内存限制：128MB lucy 的老师为了倡导废品回收，给大家布置了一项作业：利用有限的空间回收最有价值的 $k$ 件废品（即件数 $\le k$ ）。然而，这些废品也是分种类的，它们共有 $A, B$ 两种类型，而 $k$ 件废品是指在 $A, B$ 两种中各拿 $k$ 件。 现在 lucy 共收集了 $A,B$ 两种废品共 $n$ 件，它们的处理后价值是 $v_i$，其处理价格为 $p_i$。现在请你帮她求出她的最优拿取结果价值。

输入共 $n + 1$ 行： 第一行为两个整数 $n, k$ ，表示 $A, B$ 两种废品的总数量和需要拿取的废品数量； 接下来 $n$ 行，每行 $1$ 个字符 $k_i$，表示废品种类；后接 $2$ 个正整数 $v_i$ 和 $p_i$ ，分别表示处理后的价值和处理价格。

输出仅一行一个整数，表示 $A, B$ 种类废品各拿取 $k$ 件后的最优结果价值。

输入 #1

输出 #1

输入 #2

10 3
A 128 342
A 248 4379
B 729 528
B 102 7238
A 6926 239
B 2387 1023
A 1729 23479
B 3276 29
A 10 238
B 10 1

输出 #2

【数据范围】 对于 $100\%$ 的数据，保证 $1 \le n \le 1000 ， 1\le k \le 500$ 测试点编号数据范围特殊性质$1$~$5$（对于 $50\%$ 的数据）$1 \leq v_i,p_i \leq 10^5$性质 A$6$~$10$（对于 $100\%$ 的数据）$1 \leq v_i,p_i\leq 10^5$无 性质 A：保证 $p_i \le v_i$ 数据保证 $A,B$ 类物品的数量一定大于等于 $k$，$k_i$ 是字符 A 或 B。 【样例解释】 样例组 #1：最优拿取方式为： $A$ 类：拿取第 $1$ 和 $3$ 件物品； $B$ 类：拿取第 $2$ 和 $4$ 件物品； 最终价值：$(100 - 2) + (100 - 4) + (100 - 3) + (100 - 9) = 382$。

测试点编号	数据范围	特殊性质
$1$~$5$（对于 $50\%$ 的数据）	$1 \leq v_i,p_i \leq 10^5$	性质 A
$6$~$10$（对于 $100\%$ 的数据）	$1 \leq v_i,p_i\leq 10^5$	无

C++ 编辑器

输入

输出