C. Fountains

\(整体思路没错，但是我貌似太麻烦了.......\)

\(分情况讨论\)

\(Ⅰ.coin和diamond各选一个物品，这个简单\)

\(Ⅱ.在coin中选两个或者在diamond选两个\)

\(开始我想着枚举一个物品找另一个物品肯定超时\)

\(那我们可以直接预处理sumn[i]表示花费i时的最大收益,但是这样做可能这个最大收益就是枚举物品本身(重复了)\)

\(\color{Red}{至此有三种解决方案}\)

\(Ⅰ.\)

\(那我们额外记录sumn[i]时选的物品是谁，假如就是枚举的物品本身我们再对这个物品单独求解\)

\(Ⅱ.\)

\(开二维数组sumn[i][2]同时把次大值也装进去,如果余额大于等于枚举的商品且sumn[rest][0]==枚举商品价值\)

\(那么我们就取次小值，因为此时sumn[rest][0]装的值是枚举商品\)

\(Ⅲ.\)

#include <bits/stdc++.h>
using namespace std;
const int maxn=100009;
struct p{
    int v,w;
}a[maxn],b[maxn];
int cnt1,cnt2;
int vis1[100009],vis2[100009];//储存物品花费i时美感最大值
int sumn1[100009],sumn2[100009],ans;
int num1[maxn],num2[maxn],vnum1[maxn],vnum2[maxn]; 
int main()
{
    int n,m1,m2;
    cin>>n>>m1>>m2;
    for(int i=1;i<=n;i++)
    {
        int l,r;char s;
        cin>>l>>r>>s;
        if(s=='C')
        {
            if(vis1[r]<l)    vnum1[r]=cnt1+1;
            a[++cnt1].v=l,a[cnt1].w=r,vis1[r]=max(vis1[r],l);
        }
        else
        {
            if(vis2[r]<l)    vnum2[r]=cnt2+1;
            b[++cnt2].v=l,b[cnt2].w=r,vis2[r]=max(vis2[r],l);
        }
    }
    int maxn1=-1,maxn2=-1;
    for(int i=1;i<=100000;i++)
    {
        if(sumn1[i-1]<vis1[i])   num1[i]=vnum1[i];
        else    num1[i]=num1[i-1];
        if(sumn2[i-1]<vis2[i])   num2[i]=vnum2[i];
        else    num2[i]=num2[i-1];
        sumn1[i]=max(sumn1[i-1],vis1[i]);
        sumn2[i]=max(sumn2[i-1],vis2[i]);
    }
    for(int i=1;i<=cnt1;i++)
    if(a[i].w<=m1)
    {   
        maxn1=max(maxn1,a[i].v);//买得起
        if(num1[m1-a[i].w]==i)//可能存在相等(选自己)
        {
            int temp=-1;
            for(int j=1;j<=cnt1;j++)
                if(i!=j&&a[j].w<=m1-a[i].w)  
                    temp=max(temp,a[j].v);
            if(temp==-1)    continue;
            ans=max(ans,temp+a[i].v);
        } 
        else if(sumn1[m1-a[i].w]!=0)
            ans=max(ans,a[i].v+sumn1[m1-a[i].w]);
    }
    for(int i=1;i<=cnt2;i++)
    if(b[i].w<=m2)
    {
        maxn2=max(maxn2,b[i].v);
        if(num2[m2-b[i].w]==i)
        {
            int temp=-1;
            for(int j=1;j<=cnt2;j++)
                if(i!=j&&b[j].w<=m2-b[i].w)
                    temp=max(temp,b[j].v);
            if(temp==-1)    continue;
            ans=max(ans,temp+b[i].v);   
        }
        else if(sumn2[m2-b[i].w]!=0)
            ans=max(ans,b[i].v+sumn2[m2-b[i].w]);
    }
    if(maxn1!=-1&&maxn2!=-1)    ans=max(ans,maxn1+maxn2);
    cout<<ans;
}