題干：

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.

Input

The first line contains three integers?n,?c?and?d?(2?≤?n?≤?100?000,?0?≤?c,?d?≤?100?000)?— 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?≤?100?000)?— 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.

Examples

Input

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

Output

9

Input

2 4 5 2 5 C 2 1 D

Output

0

Input

3 10 10 5 5 C 5 5 C 10 11 D

Output

10

Note

In the first example Arkady should build the second fountain with beauty?4, which costs?3?coins. The first fountain he can't build because he don't have enough coins. Also Arkady should build the third fountain with beauty?5?which costs?6?diamonds. Thus the total beauty of built fountains is?9.

In the second example there are two fountains, but Arkady can't build both of them, because he needs?5?coins for the first fountain, and Arkady has only?4?coins.

題目大意：

?

解題報告：

? ?比賽的時候讓這個線段樹搞垮我了，，很多特殊情況要考慮，并且，最后卡住我的不是線段樹那一塊，而是之前的C和D兩種貨幣各選一個的那種情況，我是直接，找到就break，但是其實應該是維護一個最大值。。。因為你直接break的話只能保證cost是可符合的最大的，而保證不了val的最大性！我們需要的是val！（%%%WJH大佬）

AC代碼1：

#include<bits/stdc++.h> using namespace std; const int MAX = 100000 +5; int n,c,d,totc,totd; int cc[MAX]; int dd[MAX]; struct Node{int val,cost;Node(){}Node(int val,int cost):val(val),cost(cost){} } C[MAX],D[MAX]; struct TREE {int l,r;int val; } tree[MAX*4]; bool cmp(const Node &a,const Node &b) {return a.cost < b.cost; } void pushup(int cur) {tree[cur].val = max(tree[cur*2].val,tree[cur*2+1].val); } void buildc(int l,int r,int cur) {tree[cur].l=l;tree[cur].r=r;if(l == r) {tree[cur].val = C[l].val;return ;}int m = (l +r)/2;buildc(l,m,cur*2);buildc(m+1,r,cur*2+1);pushup(cur); } void buildd(int l,int r,int cur) {tree[cur].l=l;tree[cur].r=r;if(l == r) {tree[cur].val = D[l].val;return ;}int m = (l +r)/2;buildd(l,m,cur*2);buildd(m+1,r,cur*2+1);pushup(cur); } int query(int pl,int pr,int cur) {if(pl <= tree[cur].l && pr >= tree[cur].r) return tree[cur].val;int res = 0;if(pl <= tree[cur*2].r) res = query(pl,pr,cur*2);if(pr >= tree[cur*2+1].l) res = max(res,query(pl,pr,cur*2+1));return res; } void update(int tar,int val,int cur) {if(tree[cur].l == tree[cur].r) {tree[cur].val = val;return ;}int m = (tree[cur].l + tree[cur].r)/2;if(tar <= m) update(tar,val,cur*2);else update(tar,val,cur*2+1);pushup(cur); } signed main() {char op[10];int val,cost,flag1=0,flag2=0;cin>>n>>c>>d;for(int i = 1; i<=n; i++) {scanf("%d%d%s",&val,&cost,op);if(op[0] == 'C') {C[++totc] = Node(val,cost);}else {D[++totd] = Node(val,cost);}}sort(C+1,C+totc+1,cmp); sort(D+1,D+totd+1,cmp);int maxx=0,tmp1 = 0,tmp2 = 0,pos;for(int i = totc; i>=1; i--) {if(C[i].cost <= c) {flag1=1;tmp1 = max(tmp1,C[i].val);}}for(int i = totd; i>=1; i--) {if(D[i].cost <= d) {flag2=1;tmp2 = max(tmp2,D[i].val);}}if(flag1==0 && flag2 == 0) {printf("0\n");return 0;} if(flag1 == 1 && flag2 == 1) {maxx = tmp1 + tmp2;}if(totc == 1 && totd == 1) {if(C[1].cost > c || D[1].cost > d) {printf("0\n");return 0;}}for(int i = 1; i<=totc; i++) cc[i] = C[i].cost;for(int i = 1; i<=totd; i++) dd[i] = D[i].cost; // printf("maxx = %d\n",maxx);//處理Cif(totc != 0 ) {buildc(1,totc,1);for(int i =1; i<=totc; i++) {if(c-cc[i] < 0) break; update(i,0,1);pos = upper_bound(cc+1,cc+totc + 1,c-cc[i]) - cc-1;if(pos == 0) continue;maxx = max(maxx,C[i].val + query(1,pos,1));update(i,C[i].val,1);}}for(int i = 1; i<=MAX; i++) update(i,0,1); // printf("%d %d\n",query(1,1,1),query(1,2,1));if(totd !=0) {buildd(1,totd,1);for(int i =1; i<=totd; i++) {if(d-dd[i] < 0) break;update(i,0,1);pos = upper_bound(dd+1,dd+totd + 1,d-dd[i])- dd -1;if(pos == 0) continue;// if(dd[pos] > d-dd[i]) pos--;maxx = max(maxx,D[i].val + query(1,pos,1));update(i,D[i].val,1);}}printf("%d\n",maxx);return 0 ; } //6 4 9 //6 6 D //1 4 D //6 7 C //7 6 D //5 7 D //2 5 D//6 68 40 //1 18 D //6 16 D //11 16 D //7 23 D //16 30 D //2 20 D//3 9 5 //10 7 C //8 6 C //5 3 C

AC代碼2：（o(n^2)）

#include<bits/stdc++.h> #define ll long long using namespace std; const int MAX = 1e5 + 5 ; int n,c,d,ans; struct Node {int cost,val;char op[5]; } node[MAX]; bool cmp(const Node & a,const Node & b) {if(a.val != b.val) return a.val > b.val;return a.cost < b.cost; } int main() {cin>>n>>c>>d;for(int i = 1; i<=n; i++) {scanf("%d%d%s",&node[i].val,&node[i].cost,node[i].op);}sort(node+1,node+n+1,cmp);int cc,dd,flag,tmp;for(int i = 1; i<=n; i++) {cc = c;dd = d;flag = 0 ;if(node[i].op[0] == 'C' && node[i].cost <= c) {flag=1;cc-=node[i].cost;tmp=node[i].val;}else if(node[i].op[0] == 'D' && node[i].cost <= d) {flag=1;dd-=node[i].cost;tmp = node[i].val;}if(flag == 0) continue;for(int j = i+1; j<=n; j++) {if(node[j].op[0] == 'C' && node[j].cost <= cc) {ans = max(ans,tmp+node[j].val);break;}else if(node[j].op[0] == 'D' && node[j].cost <= dd) {ans = max(ans,tmp+node[j].val);break;}}}printf("%d\n",ans);return 0 ; }

AC代碼3：（樹狀數組）

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;const int maxn = 100000;int C[maxn+10],D[maxn+10];void add(int *tree,int k,int num) {while(k<=maxn){tree[k] = max(tree[k],num);k+=k&-k;} }int read(int *tree,int k) {int res=0;while(k){res = max(res,tree[k]);k-=k&-k;}return res; }int main(void) {int n,c,d,i,j;while(scanf("%d%d%d",&n,&c,&d)==3){memset(C,0,sizeof(C));memset(D,0,sizeof(D));int ans = 0;for(i=1;i<=n;i++){int b,p;char t[5];scanf("%d%d%s",&b,&p,t);int maxn;if(t[0] == 'C'){maxn = read(D,d);if(p > c)continue;maxn = max(maxn,read(C,c-p));add(C,p,b);}else{maxn = read(C,c);if(p > d)continue;maxn = max(maxn,read(D,d-p));add(D,p,b);}if(maxn)ans = max(ans,maxn + b);}cout << ans << endl;}return 0; }

AC代碼4：（tourist）

#include <bits/stdc++.h>using namespace std;const int N = 1234567;int pref[N], a[N], b[N]; char c[N];int solve(vector < pair <int, int> > z, int b) {sort(z.begin(), z.end());int cnt = z.size();if (cnt < 2) {return 0;}pref[0] = 0;for (int i = 0; i < cnt; i++) {pref[i + 1] = max(pref[i], z[i].second);}int i = 0;int res = 0;for (int j = cnt - 1; j >= 0; j--) {while (i < j && z[i].first + z[j].first <= b) {i++;}i = min(i, j);if (i > 0) {res = max(res, pref[i] + z[j].second);}}return res; }int main() {int n, C, D;scanf("%d %d %d", &n, &C, &D);for (int i = 0; i < n; i++) {scanf("%d %d", a + i, b + i);c[i] = getchar();while (c[i] != 'C' && c[i] != 'D') {c[i] = getchar();}}int ans = 0;{int x = 0, y = 0;for (int i = 0; i < n; i++) {if (c[i] == 'C' && b[i] <= C) {x = max(x, a[i]);}}for (int i = 0; i < n; i++) {if (c[i] == 'D' && b[i] <= D) {y = max(y, a[i]);}}if (x > 0 && y > 0) {ans = max(ans, x + y);}}{vector < pair <int, int> > z;for (int i = 0; i < n; i++) {if (c[i] == 'C') {z.push_back(make_pair(b[i], a[i]));}}ans = max(ans, solve(z, C));}{vector < pair <int, int> > z;for (int i = 0; i < n; i++) {if (c[i] == 'D') {z.push_back(make_pair(b[i], a[i]));}}ans = max(ans, solve(z, D));}printf("%d\n", ans);return 0; }

AC代碼5：（在線搞，以cost建樹（而不是排好序后用下標建樹），維護最大值）

#include<cstdio> #include<algorithm> #include<cstring> #define ll long long using namespace std; const int maxn = 100010; int a[maxn],acost[maxn],b[maxn],bcost[maxn]; struct node {int Max;int l,r; }t[maxn*4]; void build(int root,int l,int r) {t[root].l=l;t[root].r=r;//t[root].Max=-1;if(l==r)return;int mid=(l+r)>>1;build(2*root,l,mid);build(2*root+1,mid+1,r); } void update(int root,int index,int val) {int l=t[root].l,r=t[root].r;if(l==r){t[root].Max=max(t[root].Max,val);return;//}int mid=(l+r)>>1;if(index<=mid)update(2*root,index,val);elseupdate(2*root+1,index,val);t[root].Max=max(t[root*2].Max,t[root*2+1].Max); } int query(int root,int ql,int qr) {int l=t[root].l;int r=t[root].r;if(l==ql&&r==qr){return t[root].Max;}int mid=(l+r)>>1;if(qr<=mid)return query(2*root,ql,qr);else if(ql>mid)return query(2*root+1,ql,qr);elsereturn max(query(2*root,ql,mid),query(2*root+1,mid+1,qr));//2*root+1 } int main() {int N,C,D;while(~scanf("%d%d%d",&N,&C,&D)){int acnt=0,bcnt=0;char ch;int c,w;int Maxc=-1;for(int i=0;i<N;i++){scanf("%d%d %c",&c,&w,&ch);if(ch=='C'){a[acnt]=c;acost[acnt++]=w;}else if(ch=='D'){b[bcnt]=c;bcost[bcnt++]=w;}Maxc=max(w,Maxc);}int ans=-1;int res1=-1,res2=-1;for(int i=0;i<acnt;i++){if(C>=acost[i])res1=max(res1,a[i]);}for(int i=0;i<bcnt;i++){if(D>=bcost[i])res2=max(res2,b[i]);}if(res1!=-1&&res2!=-1)ans=res1+res2;Maxc=max(Maxc,max(C,D));build(1,1,Maxc+10);for(int i=0;i<acnt;i++){int res=-1;if(C>acost[i])res=query(1,1,C-acost[i]);update(1,acost[i],a[i]);if(res!=-1)ans=max(ans,a[i]+res);}build(1,1,Maxc);for(int i=0;i<bcnt;i++){int res=-1;if(D>bcost[i])res=query(1,1,D-bcost[i]);update(1,bcost[i],b[i]);if(res!=-1)ans=max(ans,b[i]+res);}if(ans!=-1)printf("%d\n",ans);elseprintf("0\n");} }

AC代碼6：（維護最大價值和次大價值 + 前綴和）（感覺這個題解有問題？）

#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second #define PII pair<ll , ll > typedef long long ll; const int N = 100005;int n; ll C, D; PII c[N], d[N]; ll ans1[N][2], ans2[N][2]; int cnt1=0, cnt2=0; //init函數中均可加等號 void Init() {sort(c+1, c+1+cnt1);sort(d+1, d+1+cnt2);ll mx1=0, mx2=0;rep(i,1,cnt1){if(mx1 < c[i].se){mx2=mx1, mx1=c[i].se;ans1[c[i].fi][0]=mx1;ans1[c[i].fi][1]=mx2;}else if(mx2 < c[i].se){mx2=c[i].se;ans1[c[i].fi][0]=mx1;//可注釋ans1[c[i].fi][1]=mx2;}}mx1=0, mx2=0;rep(i,1,cnt2){if(mx1 < d[i].se){mx2=mx1, mx1=d[i].se;ans2[d[i].fi][0]=mx1;ans2[d[i].fi][1]=mx2;}else if(mx2 < d[i].se){mx2=d[i].se;ans2[d[i].fi][0]=mx1;//可注釋ans2[d[i].fi][1]=mx2;}}rep(i,1,max(C,D)) rep(j,0,1){ans1[i][j]=max(ans1[i][j], ans1[i-1][j]);ans2[i][j]=max(ans2[i][j], ans2[i-1][j]);} } int main() {scanf("%d%lld%lld", &n, &C, &D);ll bi, pi; char ch;rep(i,1,n){scanf("%lld%lld%*c%c", &bi, &pi, &ch);if(ch=='C') c[++cnt1]=MP(pi, bi);else d[++cnt2]=MP(pi, bi);}Init();ll sum1=0;if(ans1[C][0] && ans2[D][0])sum1 = max(sum1, ans1[C][0]+ans2[D][0]);ll sum2=0, sum3=0;rep(i,1,cnt1){ll ret=C-c[i].fi;if(ret>0){if(ans1[ret][0]==c[i].se){if(ans1[ret][1])sum2 = max(sum2, c[i].se+ans1[ret][1]);}else{if(ans1[ret][0])sum2 = max(sum2, c[i].se+ans1[ret][0]);}}}rep(i,1,cnt2){ll ret=D-d[i].fi;if(ret>0){if(ans2[ret][0]==d[i].se){if(ans2[ret][1])sum3 = max(sum3, d[i].se+ans2[ret][1]);}else{if(ans2[ret][0])sum3 = max(sum3, d[i].se+ans2[ret][0]);}}}printf("%lld\n", max(sum1, max(sum2, sum3)));return 0; }

AC代碼7：（還是自己寫的那個線段樹，只是將upperbound部分進行了優化，快了將近50ms）

#include<bits/stdc++.h> using namespace std; const int MAX = 100000 +5; int n,c,d,totc,totd; int cc[MAX]; int dd[MAX]; struct Node{int val,cost;Node(){}Node(int val,int cost):val(val),cost(cost){} } C[MAX],D[MAX]; struct TREE {int l,r;int val; } tree[MAX*4]; bool cmp(const Node &a,const Node &b) {if(a.cost != b.cost)return a.cost < b.cost;return a.val > b.val; } void pushup(int cur) {tree[cur].val = max(tree[cur*2].val,tree[cur*2+1].val); } void buildc(int l,int r,int cur) {tree[cur].l=l;tree[cur].r=r;if(l == r) {tree[cur].val = C[l].val;return ;}int m = (l +r)/2;buildc(l,m,cur*2);buildc(m+1,r,cur*2+1);pushup(cur); } void buildd(int l,int r,int cur) {tree[cur].l=l;tree[cur].r=r;if(l == r) {tree[cur].val = D[l].val;return ;}int m = (l +r)/2;buildd(l,m,cur*2);buildd(m+1,r,cur*2+1);pushup(cur); } int query(int pl,int pr,int cur) {if(pl <= tree[cur].l && pr >= tree[cur].r) return tree[cur].val;int res = 0;if(pl <= tree[cur*2].r) res = query(pl,pr,cur*2);if(pr >= tree[cur*2+1].l) res = max(res,query(pl,pr,cur*2+1));return res; } void update(int tar,int val,int cur) {if(tree[cur].l == tree[cur].r) {tree[cur].val = val;return ;}int m = (tree[cur].l + tree[cur].r)/2;if(tar <= m) update(tar,val,cur*2);else update(tar,val,cur*2+1);pushup(cur); } int main() {char op[10];int val,cost,flag1=0,flag2=0;cin>>n>>c>>d;for(int i = 1; i<=n; i++) {scanf("%d%d%s",&val,&cost,op);if(op[0] == 'C') {C[++totc] = Node(val,cost);}else {D[++totd] = Node(val,cost);}}sort(C+1,C+totc+1,cmp); sort(D+1,D+totd+1,cmp);int maxx=0,tmp1 = 0,tmp2 = 0,pos;for(int i = totc; i>=1; i--) {if(C[i].cost <= c) {flag1=1;tmp1 = max(tmp1,C[i].val);}}for(int i = totd; i>=1; i--) {if(D[i].cost <= d) {flag2=1;tmp2 = max(tmp2,D[i].val);}}if(flag1==0 && flag2 == 0) {printf("0\n");return 0;} if(flag1 == 1 && flag2 == 1) {maxx = tmp1 + tmp2;}if(totc == 1 && totd == 1) {if(C[1].cost > c || D[1].cost > d) {printf("0\n");return 0;}}for(int i = 1; i<=totc; i++) cc[i] = C[i].cost;for(int i = 1; i<=totd; i++) dd[i] = D[i].cost; // printf("maxx = %d\n",maxx);//處理Cif(totc != 0 ) {buildc(1,totc,1);for(int i =1; i<totc; i++) {if(c-cc[i] < 0) break; // update(i,0,1);pos = upper_bound(cc+i+1,cc+totc + 1,c-cc[i]) - (cc/*+i*/)-1;if(pos == i) continue;maxx = max(maxx,C[i].val + query(i+1,pos,1)); // update(i,C[i].val,1);}} // printf("%d %d\n",query(1,1,1),query(1,2,1));if(totd !=0) {buildd(1,totd,1);for(int i =1; i<totd; i++) {if(d-dd[i] < 0) break; // update(i,0,1);pos = upper_bound(dd+i+1,dd+totd + 1,d-dd[i])- (dd/*+i*/) -1;if(pos == i) continue;// if(dd[pos] > d-dd[i]) pos--;maxx = max(maxx,D[i].val + query(i+1,pos,1)); // update(i,D[i].val,1);}}printf("%d\n",maxx);return 0 ; } //6 4 9 //6 6 D //1 4 D //6 7 C //7 6 D //5 7 D //2 5 D//6 68 40 //1 18 D //6 16 D //11 16 D //7 23 D //16 30 D //2 20 D//3 9 5 //10 7 C //8 6 C //5 3 C

總結：

? ? 對于這一道經典的題目，我想，可以總結的東西還是很多的。

? ?對于任何數據結構（包括線段樹等，包括棧隊列等），首先需要看的就是能否進入，或者說，這項功能能否執行? 的問題。比如棧，進行pop和top操作的時候要想，是否需要先判斷是否棧為空呢？因為為空了就沒法進行操作了呀。同理，對于線段樹，我們也要想，我們能否建樹呢？建樹后，能否進行查詢呢？即，這個傳參是合法的嗎？（這兩條思考，分別對應了AC代碼1中的，if(totc!=0),,,,if(c-cc[i] < 0) break; 這兩句）

? ?其次是這一塊的處理，也經常容易忽略：（一個比較可行的解決辦法就是自己造數據的時候這些邊界情況都考慮一下）（好像說了一堆廢話）

if(flag1==0 && flag2 == 0) {printf("0\n");return 0;} if(flag1 == 1 && flag2 == 1) {maxx = tmp1 + tmp2;}if(totc == 1 && totd == 1) {if(C[1].cost > c || D[1].cost > d) {printf("0\n");return 0;}}

將ac代碼1修改成AC代碼7：

? ? ?改1：for(int i =1; i<totc; i++) {

? ? ?改2：if(pos == i) continue;

? ? ?改3：maxx = max(maxx,C[i].val + query(i+1,pos,1));//這里query中是從i+1開始的

? ? ?改4：每個for中都可以注釋掉兩個update函數。（因為就沒用了）

?

還有一些可總結的：

? ? lowerbound? upperbound的時候，如果不是對整個數列進行，比如是對[ l , r ]進行，那么upper的可能值就是[?l , r+1 ]這個區間內的值。（即upper出來的pos，肯定大于等于l，小于等于r+1），同理 lowerbound出來的值略有不同，區間是[ l , r ]（我感覺是這樣？）

? ?還有就是，對[ l , r ]進行的時候，但是還是要 -a? 而不是-(a+i-1)? 也就是int pos = lower_bound(a+i,a+i+1,val) - a;這樣就可以，因為你最后需要的還是在原數組中的下標呀。

? 總之做題還是要在仔細一些吧。

另一個代碼:https://blog.csdn.net/SSimpLe_Y/article/details/71702915

總結

以上是生活随笔為你收集整理的*【CodeForces - 799C】Fountains （线段树 或 树状数组，类似二元组问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。