AGC-018 C

题意：

有$X + Y + Z$个人，第$i$个人有$Ai$个金币，$Bi$个银币，$Ci$个铜币。选出$X$个人获得其金币，选出$Y$ 个人获得其银币，选出$Z$个人获得其铜币，在不重复选某个人的前提下，最大化获得的币的总数。

$X + Y + Z ≤ 10^5$

题解：

一道比较好的题

首先比较显然的是这个东西可以dp，复杂度上天

考虑只有两种金币

那么我们可以通过将$ai=ai-bi$ 使得问题变成一维取最大值，那就可以O(n)贪心了

对于这道题同理，我们先将$ai=ai-ci$ $bi=bi-ci$

那么变成了有两种物品，其$a$取$k1$个，$b$取$k2$个

然后呢现在肯定没法直接贪心了

但是这种和顺序无关的我们先按照ai递减排序一下

我们去枚举最后一个选的ai

那么对于它之前的，我们一定要么用了ai要么用了bi，而对于后面的，一定选最大的几个bi

对于前面的，等价于第一个问题然后用堆维护一下就行了

巴特西