C. Fountains（最大值树状数组）

最大值树状数组）"/>

C. Fountains（最大值树状数组）

有 n 个泉水，c 枚金币，d 枚钻石，每个泉水可以带来 b 点欢乐值，但要消耗 p 枚金币或钻石，只能买两座泉水，问最大的快乐值 

这个题明显贪心啊 

如果两种泉水各买一座还好，但是有可能一种泉水买两坐，剩下的一种不买，所以利用树状数组求区间最大值

const int N=2e5+5;int n,m,t;int i,j,k;int c[N],d[N];int get_max(int x,int *aim)//1~x 的最大值
{int ans=0;while(x){ans=max(ans,aim[x]);x-=lowbit(x);}return ans;
}
void update(int x,int val,int *aim)
{while(x<=N){aim[x]=max(aim[x],val);x+=lowbit(x);}
}
int main()
{IOS;for(int C,D;cin>>n>>C>>D;){int ans=0,maxx;for(i=1;i<=n;i++){int b,p; char ch;cin>>b>>p>>ch;maxx=0;if(ch=='C'){maxx=get_max(D,d);//用 D 能买到的最大值if(p>C) continue;maxx=max(maxx,get_max(C-p,c));//将当前的这个买下，用剩下的钱再买一个 cupdate(p,b,c);}else{maxx=get_max(C,c);if(p>D) continue;maxx=max(maxx,get_max(D-p,d));update(p,b,d);}if(maxx)ans=max(maxx+b,ans);}cout<<ans<<endl;}//PAUSE;
}