[#413c] Fountains

http://codeforces.com/contest/799/problem/C

解题关键：树状数组取最大值，注意先搜索，后加入，此种情况可以取出最大值。

为什么可以取到最大值？

1、当分别用两种硬币购买时，一定可以全部访问完。

2、用一种硬币时，依然可以遍历完

 1 #include<bits/stdc++.h>
 2 #define fo(i,a,b) for(int i=(a);i<(b);i++)
 3 #define mp make_pair
 4 #define pb push_back
 5 using namespace std;
 6 typedef long long ll;//要建两颗树状数组 
 7 int C[100002],D[100002],maxn=100002;
 8 int read(int *tree,int i){
 9     int s=0;
10     while(i>0){
11         s=max(s,tree[i]);
12         i-=i&-i;
13     }
14     return s;
15 }
16 void add(int *tree,int i,int x){
17     while(i<=maxn){
18         tree[i]=max(tree[i],x);
19         i+=i&-i;
20     }
21 }
22 //必须先搜索，再加入 
23 int b,p;
24 char a;
25 int main(){
26     int n,c,d,mm,ans=0;
27     cin>>n>>c>>d;
28     fo(i,0,n){
29         cin>>b>>p>>a;
30         if(a=='C'){
31             mm=read(D,d);
32             if(p>c) continue;
33             mm=max(mm,read(C,c-p));
34             add(C,p,b);
35         }
36         else{
37             mm=read(C,c);
38             if(p>d) continue;
39             mm=max(mm,read(D,d-p));
40             add(D,p,b);
41         }
42         if(mm){
43             ans=max(ans,mm+b);
44         }
45     }
46     cout<<ans<<endl;
47 }