题目大意

给你\(X+Y+Z\)个三元组\((x_i,y_i,z_i)\)。

然后选\(X\)个\(x_i\)，选\(Y\)个\(y_i\)，选\(Z\)个\(z_i\)。

每个三元组只能选择其中一个。

问最大的和。

思考历程

想不到贪心……

于是只能\(DP\)了……

\(DP\)就不用说了吧……

正解

首先考虑\(X=0\)的情况：

按照\(z-y\)排个序，前面\(Z\)个选择\(z\)，后面\(Y\)个选择\(y\)。

这就是一个可撤销贪心的思路，可以看成先全部选\(y\)，然后选\(Z\)个\(z-y\)最大的。

然后就是普通的情况。首先强制所有选\(x\)，然后按照\(z-y\)排个序。

枚举\(z-y\)的分界点，在前面的选\(z\)或\(x\)，在后面的选\(y\)或\(x\)。

那么就变成了上面的问题：在\(x\)和\(z\)中选择，显然是\(z\)选\(z-x\)最大的\(Z\)个。

这个东西可以用数据结构维护，只不过会TLE。

于是可以搞个桶，用一个指针\(l\)表示当前选的最小的数在桶中的位置。

新加进来一个树的时候，用它在同种的位置和\(l\)比较一下，如果更大，说明\(l\)废了，于是就将它加进桶中，然后\(l\)往后找下一个最小的。

很显然，随着分界点朝右延伸，\(l\)一定是越来越大。

右边的同理。

如果排序也用桶排序，那就可以达到真正的\(O(n)\)

代码

然而我懒得打桶排序，就直接用自带的快排过去了……

using namespace std;#include 
    
     #include 
     
      #include 
      
       #define N 1500010#define ll long longinline int input(){    char ch=getchar();    while (ch<'0' || '9'
       
        _t[b].z-_t[b].y;}inline bool cmp2(int a,int b){return c[a]