Fountains

time limit per test 2 second memory limit per test 256 megabytes
Arkady plays Gardenscapes a lot. Arkady wants to build two new fountains. There are n available fountains, for each fountain its beauty and cost are known. There are two types of money in the game: coins and diamonds, so each fountain cost can be either in coins or diamonds. No money changes between the types are allowed.

Help Arkady to find two fountains with maximum total beauty so that he can buy both at the same time.

传送门:CF799C

Input

The first line contains three integers n, c and d (2≤n≤100000, 0≤c,d≤100000) — the number of fountains, the number of coins and diamonds Arkady has.
The next n lines describe fountains. Each of these lines contain two integers bi and pi (1≤bi,pi≤100000) — the beauty and the cost of the i-th fountain, and then a letter “C” or “D”, describing in which type of money is the cost of fountain i: in coins or in diamonds, respectively.

Output

Print the maximum total beauty of exactly two fountains Arkady can build. If he can’t build two fountains, print 0.

Sample Input

1
2
3
4
5
6
7
8
3 7 6
10 8 C
4 3 C
5 6 D

2 4 5
2 5 C
2 1 D

Sample Output

1
2
3
9

0

题解

注意注意注意 对数的话一定是有先后顺序的!!!那么对于一个找另外一个就可以在它前面找或者在他后面找 很重要!!!
这道题搞明白了对数后用前缀最大数组和线段树都能做

AC code:(不包含输入类)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
while(sc.hasNext()){
int n=sc.nextInt();
int c=sc.nextInt();
int d=sc.nextInt();
ArrayList<F>list1=new ArrayList<F>();
ArrayList<F>list2=new ArrayList<F>();
int max1=-1;
int max2=-1;
boolean c1=false;
boolean c2=false;
for(int i=0;i<n;i++){
int v=sc.nextInt();
int cost=sc.nextInt();
String s=sc.next();
if(s.equals("C")){
if(cost<=c){
max1=Math.max(max1, v);
c1=true;
}
list1.add(new F(v,cost));
}else{
if(cost<=d){
max2=Math.max(max2, v);
c2=true;
}
list2.add(new F(v,cost));
}
}
Collections.sort(list1);
Collections.sort(list2);
SegTree tree1=new SegTree(list1.size());
SegTree tree2=new SegTree(list2.size());
for(int i=0;i<list1.size();i++) tree1.update(i, list1.get(i).v);
int max=tree1.query(0, 1);
System.out.println(max);
for(int i=0;i<list2.size();i++) tree2.update(i, list2.get(i).v);
/*int[]cv=new int[list1.size()];
int[]dv=new int[list2.size()];
for(int i=0;i<list1.size();i++){
if(i==0)cv[i]=list1.get(0).v;
else cv[i]=Math.max(cv[i-1],list1.get(i).v);
}
for(int i=0;i<list2.size();i++){
if(i==0)dv[i]=list2.get(0).v;
else dv[i]=Math.max(dv[i-1],list2.get(i).v);
}*/
if(c1==true&&c2==true){
int res=max1+max2;
res=Math.max(res, findMax(c,list1,tree1));
res=Math.max(res, findMax(d,list2,tree2));
pw.println(res);
}else{
int res=-1;
res=Math.max(res, findMax(c,list1,tree1));
res=Math.max(res, findMax(d,list2,tree2));
if(res==-1) pw.println(0);
else pw.println(res);
}
pw.flush();
}

}
static int findMax(int c,ArrayList<F>list,SegTree tree){
int res=-1;
for(int i=0;i<list.size();i++){
int start=0;
int end=i-1;
int result=-1;
while(start<=end){
int mid=(start+end)/2;
if(list.get(mid).c+list.get(i).c<=c){
result=mid;
start=mid+1;
}
else{
end=mid-1;
}
}
if(result!=-1){
int temp=list.get(i).v;
int max=tree.query(0, result+1);
//System.out.println(i+" "+max);
res=Math.max(res, max+temp);
tree.update(i, temp);
}
}
return res;
}
/*static int findMax(int c,ArrayList<F>list,int[]shu){
int max=-1;
for(int i=0;i<list.size();i++){
int result=-1;
int t=list.get(i).c;
int v=list.get(i).v;
int start=0;
int end=i-1;
while(start<=end){
int mid=(start+end)/2;
if(list.get(mid).c+t<=c){
result=mid;
start=mid+1;
}else{
end=mid-1;
}
}
if(result!=-1){
max=Math.max(max, v+shu[result]);
}
}
return max;
}*/

}
class SegTree{
int[]tree=new int[4005000];
int n;
SegTree(int n){
this.n=1;
while(this.n<n){
this.n*=2;
}
for(int i=0;i<2*this.n;i++)tree[i]=0;
}
void update(int k,int value){
k=k+n-1;
tree[k]=value;
while(k>0){
k=(k-1)/2;
tree[k]=Math.max(tree[k*2+1], tree[k*2+2]);
}
}
int hquery(int a,int b,int k,int l,int r){
if(r<=a||b<=l)return 0;
if(a<=l&&r<=b)return tree[k];
else{
int left=hquery(a,b,2*k+1,l,(l+r)/2);
int right=hquery(a,b,2*k+2,(l+r)/2,r);
return Math.max(left, right);
}
}
int query(int l,int r){
return hquery(l,r,0,0,n);
}
}
class F implements Comparable<F>{
int v;
int c;
F(int v,int c){
this.v=v;
this.c=c;
}
@Override
public int compareTo(F a) {
if(this.c<a.c)return -1;
if(this.c>a.c)return 1;
if(this.v<a.v)return -1;
if(this.v>a.v)return 1;
return 0;
}
}