CF799C Fountains

CF799C Fountains
可以上数据结构维护，当然也可以大力分类讨论。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,A,B,Ct=0,Dt=0;
struct data{
    int b;
    int p;
    bool operator <(const data &_B)const{
        return p<_B.p;
    }
}C[100005],D[100005];
inline int slv1(){
    if((!Ct)||(!Dt)){
        return 0;
    }
    if(C[1].p>A||D[1].p>B){
        return 0;
    }
    int rtC=0,rtD=0,pC=1,pD=1;
    while(pC<=Ct&&C[pC].p<=A){
        rtC=max(rtC,C[pC].b);
        ++pC;
    }
    while(pD<=Dt&&D[pD].p<=B){
        rtD=max(rtD,D[pD].b);
        ++pD;
    }
    return rtC+rtD;
}
//AC[i]表示，剩余为i时的最大收益，rAC[i]表示，剩余大于等于i时的最大收益。 sAC与srAC分别表示它们的位置。 
int AC[100005],rAC[100005],sAC[100005],srAC[100005],sbAC[100005];
inline int slv2(){
    if(Ct<2){
        return 0;
    }
    if(C[1].p+C[2].p>A){
        return 0;
    }
    int rtC=0;
    for(int i=1;i<=Ct&&C[i].p<=A;++i){
        if(AC[A-C[i].p]<C[i].b){
            AC[A-C[i].p]=C[i].b,sAC[A-C[i].p]=i;
        }
    }
    for(int i=A;i>=1;--i){
        if(rAC[i+1]>AC[i]){
            rAC[i]=rAC[i+1];
            srAC[i]=srAC[i+1]; 
        }else{
            rAC[i]=AC[i];
            srAC[i]=sAC[i]; 
        }
    }
    for(int i=1;i<=Ct;++i){
        if(i!=srAC[C[i].p]&&rAC[C[i].p]){
            rtC=max(rtC,C[i].b+rAC[C[i].p]);
        }else{
        	//rtC=max(rtC,C[i].b+C[i-1].b);
		}
    }
    return rtC;
}

int BD[100005],rBD[100005],sBD[100005],srBD[100005];
inline int slv3(){
    if(Dt<2){
        return 0;
    }
    if(D[1].p+D[2].p>B){
        return 0;
    }
    int rtD=0;
    for(int i=1;i<=Dt&&D[i].p<=B;++i){
        if(BD[B-D[i].p]<D[i].b){
            BD[B-D[i].p]=D[i].b,sBD[B-D[i].p]=i;
        }
    }
    for(int i=B;i>=1;--i){
        if(rBD[i+1]>BD[i]){
            rBD[i]=rBD[i+1];
            srBD[i]=srBD[i+1]; 
        }else{
            rBD[i]=BD[i];
            srBD[i]=sBD[i]; 
        }
    }
    for(int i=1;i<=Dt;++i){
        if(i!=srBD[D[i].p]&&rBD[D[i].p]){
            rtD=max(rtD,D[i].b+rBD[D[i].p]);
        }
    }
    return rtD;
}
void init(){
    scanf("%d%d%d",&n,&A,&B);
    char ch[5];
    int x,y;
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x,&y);
        cin>>ch;
        if(ch[0]=='C'){
            C[++Ct]=(data){x,y};
        }else{
            D[++Dt]=(data){x,y};
        }
    }
    sort(C+1,C+1+Ct);
    sort(D+1,D+1+Dt);
    int ans=0;
    ans=max(ans,slv1());
    ans=max(ans,slv2());
    ans=max(ans,slv3());
    printf("%d\n",ans);
}
int main(){
    init();
    return 0;
}