fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define loo(i,a,b) for(i=a;i<b;i++)
  5. #define lo(i,a,b) for(i=a;i>=b;i--)
  6. #define mod 1000000007
  7. #define fiv 100000
  8. #define PI 3.1415926535897932384626433832795
  9. bool myfunction(ll i,ll j) { return (i>j); }
  10. #define qua 100005
  11. pair<ll,ll> coins[qua],diamonds[qua];
  12. ll aa[qua],ab[qua];
  13. pair<ll,ll> seta[qua],setb[qua];
  14. int main() 
  15. {
  16.   ios::sync_with_stdio(false);
  17.   ll n,c,d,a,b,i,j,k=0,l=0,m=0,beauty=0;
  18.   char p;
  19.   cin>>n>>c>>d;
  20.   j=0;
  21.   loo(i,0,n)
  22.   {
  23.   	cin>>a>>b>>p;
  24.  
  25.  
  26.   	if(p=='C')
  27.   	{
  28.   		coins[j++]={b,a};
  29.   		if(c>=b)
  30.   			k=max(k,a);
  31.   		if(a>seta[b].first)
  32.   			{ seta[b].second=seta[b].first; seta[b].first=a; }
  33.   		else if(a>seta[b].second)
  34.   			seta[b].second=a;
  35.   	}	
  36.  
  37.  
  38.   	else
  39.   	{
  40.   		diamonds[l++]={b,a};
  41.   		if(d>=b)
  42.   			m=max(m,a);
  43.   		if(a>setb[b].first)
  44.   			{ setb[b].second=setb[b].first; setb[b].first=a; }
  45.   		else if(a>setb[b].second)
  46.   			setb[b].second=a;
  47.   	}	
  48.   }
  49.  
  50.  
  51.   if(k!=0&&m!=0) beauty=k+m;
  52.   //cout<<beauty<<" ";
  53.   //both from coins
  54.  
  55. sort(coins,coins+j);
  56. //precomputing prefix beauty
  57.  
  58. loo(i,0,j)
  59. {
  60. 	if(i==0)
  61. 		aa[i]=coins[i].second;
  62. 	else
  63. 		aa[i]=max(aa[i-1],coins[i].second);
  64. }
  65.  
  66.  
  67. k=0; m=0;
  68. loo(i,1,j)
  69. {
  70. 	a=coins[i].first;
  71. 	m=seta[a].first;
  72. 	a=c-a;
  73. 	ll s=0,mid=0,e=i-1; k=0;
  74. //binary search
  75.  
  76. 	while(s!=e)
  77. 	{
  78. 		mid=(s+e)/2;
  79. 		if(a==coins[mid].first)
  80. 			break;
  81. 		else if(a>coins[mid].first)
  82. 			s=mid+1;
  83. 		else if(a<coins[mid].first)
  84. 			e=mid-1;
  85. 	}
  86.  
  87.  
  88. 	if(i==1) 
  89. 	{
  90. 		if(a>=coins[0].first)
  91. 		{
  92. 			if(coins[0].first==coins[1].first)
  93. 			 	k=seta[coins[0].first].second; 
  94. 			else
  95. 				k=seta[coins[0].first].first;
  96. 		}		
  97. 	}
  98.  
  99. 	else if(a==coins[mid].first)
  100. 	{
  101. 		if(coins[mid].first==coins[i].first)
  102. 			k=max(seta[coins[i].first].second,aa[i]);
  103. 		else
  104. 			k=max(seta[coins[mid].first].first,aa[mid]);
  105. 	}	
  106.  
  107. 	else if(s==e&&s!=0)
  108. 	{
  109. 		s--;
  110. 		mid=s;
  111.  
  112. 		if(coins[mid].first==coins[i].first)
  113. 			k=max(seta[coins[i].first].second,aa[i]);
  114. 		else
  115. 			k=max(seta[coins[mid].first].first,aa[mid]);
  116. 	}
  117. 	if(k!=0)
  118. 	beauty=max(beauty,m+k);
  119. }
  120.  
  121.  
  122.  
  123. //both from diamonds
  124.  
  125. sort(diamonds,diamonds+l);
  126. //precomputing prefix beauty
  127. k=0; m=0;
  128. loo(i,0,l)
  129. {
  130. 	if(i==0)
  131. 		ab[i]=diamonds[i].second;
  132. 	else
  133. 		ab[i]=max(ab[i-1],diamonds[i].second);
  134. }
  135.  
  136.  
  137. k=0; m=0;
  138. loo(i,1,l)
  139. {
  140. 	a=diamonds[i].first;
  141. 	m=setb[a].first;
  142. 	a=d-a;
  143. 	ll s=0,mid=0,e=i-1; k=0;
  144. //binary search
  145.  
  146. 	while(s!=e)
  147. 	{
  148. 		mid=(s+e)/2;
  149. 		if(a==diamonds[mid].first)
  150. 			break;
  151. 		else if(a>diamonds[mid].first)
  152. 			s=mid+1;
  153. 		else if(a<diamonds[mid].first)
  154. 			e=mid-1;
  155. 	}
  156.  
  157.  
  158. 	if(i==1) 
  159. 	{
  160. 		if(a>=diamonds[0].first)
  161. 		{
  162. 			if(diamonds[0].first==diamonds[1].first)
  163. 			 	k=setb[diamonds[0].first].second; 
  164. 			else
  165. 				k=setb[diamonds[0].first].first;
  166. 		}		
  167. 	}
  168.  
  169. 	else if(a==diamonds[mid].first)
  170. 	{
  171. 		if(diamonds[mid].first==diamonds[i].first)
  172. 			k=max(setb[diamonds[i].first].second,ab[i]);
  173. 		else
  174. 			k=max(setb[diamonds[mid].first].first,ab[mid]);
  175. 	}	
  176.  
  177. 	else if(s==e&&s!=0)
  178. 	{
  179. 		s--;
  180. 		mid=s;
  181.  
  182. 		if(diamonds[mid].first==diamonds[i].first)
  183. 			k=max(setb[diamonds[i].first].second,ab[i]);
  184. 		else
  185. 			k=max(setb[diamonds[mid].first].first,ab[mid]);
  186. 	}
  187. 	if(k!=0)
  188. 	beauty=max(beauty,m+k);
  189. }
  190.  
  191. cout<<beauty;
  192. }
Success #stdin #stdout 0s 23056KB
comments (?)
stdin
copy 
3 10 10
5 5 C
5 5 C
10 11 D
stdout
copy 
10
https://ideone.com/C652Y9
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!