fork download
copy 
  1. //The Theatre Problem Problem Code: THEATRE
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. struct node{
  5. 	int freq;
  6. 	map<char,int> M;
  7. 	map<int,int> T,S;
  8. 	int ans;
  9. 	int sss;
  10. 	int c;
  11. };
  12. int main(){
  13. 	//freopen("input.txt","r",stdin);
  14. 	//freopen("output.txt","w",stdout);
  15. 	ios_base::sync_with_stdio(false);
  16. 	cin.tie(0);
  17. 	int t,ANS=0;
  18. 	cin>>t;
  19. 	while(t--){
  20. 		int n;
  21. 		cin>>n;
  22. 		bool fill = false;
  23. 		vector<pair<char,int>> G[13];
  24. 		int loss = 0;
  25. 		int A12=0,A3=0,A6=0,A9=0,B12=0,B3=0,B6=0,B9=0,C12=0,C3=0,C6=0,C9=0,D12=0,D3=0,D6=0,D9=0;
  26. 		while(n--){
  27. 			char m;
  28. 			int a;
  29. 			cin>>m>>a;
  30. 			if(m == 'A'){
  31. 				if(a == 12)A12++;
  32. 				else if(a == 3)A3++;
  33. 				else if(a == 6)A6++;
  34. 				else if(a == 9)A9++;
  35. 			}else if(m == 'B'){
  36. 				if(a == 12)B12++;
  37. 				else if(a == 3)B3++;
  38. 				else if(a == 6)B6++;
  39. 				else if(a == 9)B9++;
  40. 			}else if(m == 'C'){
  41. 				if(a == 12)C12++;
  42. 				else if(a == 3)C3++;
  43. 				else if(a == 6)C6++;
  44. 				else if(a == 9)C9++;
  45. 			}else {
  46. 				if(a == 12)D12++;
  47. 				else if(a == 3)D3++;
  48. 				else if(a == 6)D6++;
  49. 				else if(a == 9)D9++;
  50. 			}
  51. 		}
  52. 		G[12].push_back({'A',A12});
  53. 		G[12].push_back({'B',B12});
  54. 		G[12].push_back({'C',C12});
  55. 		G[12].push_back({'D',D12});
  56. 		G[3].push_back({'A',A3});
  57. 		G[3].push_back({'B',B3});
  58. 		G[3].push_back({'C',C3});
  59. 		G[3].push_back({'D',D3});
  60. 		G[6].push_back({'A',A6});
  61. 		G[6].push_back({'B',B6});
  62. 		G[6].push_back({'C',C6});
  63. 		G[6].push_back({'D',D6});
  64. 		G[9].push_back({'A',A9});
  65. 		G[9].push_back({'B',B9});
  66. 		G[9].push_back({'C',C9});
  67. 		G[9].push_back({'D',D9});
  68. 		queue<node> Q;
  69. 		//cout<<G[0][0].first<<" "<<G[0][1].second<<endl;
  70. 		for(vector<pair<char,int>>::iterator it = G[12].begin();it!=G[12].end();it++){
  71. 			map<char,int> M;
  72. 			map<int,int> T,S;
  73. 			if(it->second == 0)Q.push({it->second,M,T,S,-100,12,1});
  74. 			else{
  75. 				M[it->first]++;
  76. 				T[100]++;
  77. 				S[12]++;
  78. 				Q.push({it->second,M,T,S,100*it->second,12,1});
  79. 				T[100]=0;
  80. 				T[75]++;
  81. 				Q.push({it->second,M,T,S,75*it->second,12,1});
  82. 				T[75]=0;
  83. 				T[50]++;
  84. 				Q.push({it->second,M,T,S,50*it->second,12,1});
  85. 				T[50]=0;
  86. 				T[25]++;
  87. 				Q.push({it->second,M,T,S,25*it->second,12,1});	
  88. 			}
  89. 		}
  90. 		int aans = 0,k=0;
  91. 		while(!Q.empty()){
  92. 			node X = Q.front();
  93. 			Q.pop();
  94. 			if(k<X.c){
  95. 				aans =X.ans;
  96. 				k = X.c;
  97. 			}else if(k == X.c){
  98. 				aans = max(aans,X.ans);
  99. 			}
  100. 			if(X.sss == 12){
  101. 				int hhh=0;
  102. 				for(vector<pair<char,int>>::iterator it = G[3].begin();it!=G[3].end();it++){
  103. 					if(X.M[it->first] == 0){
  104. 						hhh++;
  105. 						map<char,int> MM = X.M;
  106. 						if(it->second == 0)Q.push({it->second,MM,X.T,X.S,X.ans-100,3,X.c+1});
  107. 						else{
  108. 						MM[it->first]++;
  109. 						X.S[3]++;
  110. 						map<int,int> TT;
  111. 						TT = X.T;
  112. 						if(X.T[100]==0){TT[100]++;Q.push({it->second,MM,TT,X.S,X.ans+(100*it->second),3,X.c+1});}
  113. 						TT = X.T;
  114. 						if(X.T[75]==0){TT[75]++;Q.push({it->second,MM,TT,X.S,X.ans+(75*it->second),3,X.c+1});}
  115. 						TT = X.T;
  116. 						if(X.T[50]==0){TT[50]++;Q.push({it->second,MM,TT,X.S,X.ans+(50*it->second),3,X.c+1});}
  117. 						TT = X.T;
  118. 						if(X.T[25]==0){TT[25]++;Q.push({it->second,MM,TT,X.S,X.ans+(25*it->second),3,X.c+1});}
  119. 						}
  120. 					}
  121. 				}
  122. 			}else if(X.sss == 3){
  123. 				int hhh=0;
  124. 				for(vector<pair<char,int>>::iterator it = G[6].begin();it!=G[6].end();it++){
  125. 					if(X.M[it->first] == 0){
  126. 						hhh++;
  127. 						map<char,int> MM = X.M;
  128. 						if(it->second == 0)Q.push({it->second,MM,X.T,X.S,X.ans-100,6,X.c+1});
  129. 						else{
  130. 						MM[it->first]++;
  131. 						X.S[6]++;
  132. 						map<int,int> TT;
  133. 						TT = X.T;
  134. 						if(X.T[100]==0){TT[100]++;Q.push({it->second,MM,TT,X.S,X.ans+(100*it->second),6,X.c+1});}
  135. 						TT = X.T;
  136. 						if(X.T[75]==0){TT[75]++;Q.push({it->second,MM,TT,X.S,X.ans+(75*it->second),6,X.c+1});}
  137. 						TT = X.T;
  138. 						if(X.T[50]==0){TT[50]++;Q.push({it->second,MM,TT,X.S,X.ans+(50*it->second),6,X.c+1});}
  139. 						TT = X.T;
  140. 						if(X.T[25]==0){TT[25]++;Q.push({it->second,MM,TT,X.S,X.ans+(25*it->second),6,X.c+1});}
  141. 						}
  142. 					}
  143. 				}
  144. 			}else if(X.sss == 6){
  145. 				int hhh=0;
  146. 				for(vector<pair<char,int>>::iterator it = G[9].begin();it!=G[9].end();it++){
  147. 					if(X.M[it->first] == 0){
  148. 						hhh++;
  149. 						map<char,int> MM = X.M;
  150.                         if(it->second == 0)Q.push({it->second,MM,X.T,X.S,X.ans-100,9,X.c+1});
  151. 						else{
  152. 						MM[it->first]++;
  153. 						X.S[9]++;
  154. 						map<int,int> TT;
  155. 						TT = X.T;
  156. 						if(X.T[100]==0){TT[100]++;Q.push({it->second,MM,TT,X.S,X.ans+(100*it->second),9,X.c+1});}
  157. 						TT = X.T;
  158. 						if(X.T[75]==0){TT[75]++;Q.push({it->second,MM,TT,X.S,X.ans+(75*it->second),9,X.c+1});}
  159. 						TT = X.T;
  160. 						if(X.T[50]==0){TT[50]++;Q.push({it->second,MM,TT,X.S,X.ans+(50*it->second),9,X.c+1});}
  161. 						TT = X.T;
  162. 						if(X.T[25]==0){TT[25]++;Q.push({it->second,MM,TT,X.S,X.ans+(25*it->second),9,X.c+1});}
  163. 						}
  164. 					}
  165. 				}
  166. 			}
  167. 		}
  168. 		cout<<aans-loss<<"\n";
  169. 		ANS+=(aans-loss);
  170. 	}
  171. 	cout<<ANS<<"\n";
  172. 	return 0;
  173. }
Success #stdin #stdout 0s 4336KB
comments (?)
stdin
copy 
5
12
A 3
B 12
C 6
A 9
B 12
C 12
D 3
B 9
D 3
B 12
B 9
C 6
7
A 9
A 9
B 6
C 3
D 12
A 9
B 6
2
A 9
B 6
1
D 12
0
stdout
copy 
575
525
-25
-200
-400
475
https://ideone.com/9txu4c
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!