fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long long llo;
  5. #define mp make_pair
  6. #define pb push_back
  7. #define a first 
  8. #define b second
  9. #define endl '\n'
  10.  
  11. llo t;
  12. vector<llo> it[1000001];
  13. //llo dp[1000001];
  14. llo co[30];
  15. llo ma[30];
  16. llo dp[26][26];
  17. llo dp3[26][26];
  18.  
  19. llo ma2[30][30];
  20. llo dp2[30][26];
  21. int main(){
  22. 	ios_base::sync_with_stdio(false);
  23. 	cin.tie(NULL);
  24. 	cin>>t;
  25. 	while(t--){
  26. 		llo n,q;
  27. 		cin>>n>>q;
  28. 		for(llo ii=0;ii<26;ii++){
  29. 			ma[ii]=0;
  30. 			for(int j=0;j<26;j++){
  31. 				ma2[ii][j]=0;
  32. 			}
  33. 		}
  34. 		for(llo i=0;i<n;i++){
  35. 			string s;
  36. 			cin>>s;		
  37.  
  38. 			it[i].clear();
  39. 			for(llo j=0;j<26;j++){
  40. 				co[j]=0;
  41. 			}
  42. 			for(llo j=0;j<s.size();j++){
  43. 				it[i].pb(s[j]-'a');
  44. 				co[it[i].back()]++;
  45. 			}
  46. 			for(llo ii=0;ii<26;ii++){
  47. 				for(int j=0;j<26;j++){
  48. 					dp3[ii][j]=0;
  49. 				}
  50. 			}
  51.  
  52. 			for(llo j=0;j<it[i].size();j++){
  53. 				for(llo k=0;k<26;k++){
  54. 					for(llo l=k;l<26;l++){
  55. 						dp[k][l]=dp3[k][l];
  56. 						if(it[i][j]>=k and it[i][j]<=l){
  57. 							dp[k][l]=max(dp[k][l],dp3[k][it[i][j]]+1);
  58. 						}
  59. 					}
  60. 				}
  61. 				for(llo ii=0;ii<26;ii++){
  62. 					for(int j=0;j<26;j++){
  63. 						dp3[ii][j]=dp[ii][j];
  64. 					}
  65. 				}
  66. 			}
  67. 			for(llo k=0;k<26;k++){
  68. 				for(llo l=k;l<26;l++){
  69. 					ma2[k][l]=max(ma2[k][l],dp[k][l]);
  70. 				}
  71. 			}
  72. 			for(llo j=0;j<26;j++){
  73. 				ma[j]=max(ma[j],co[j]);
  74. 			}
  75. 		}
  76. 		llo ans=0;
  77. 		for(llo i=0;i<26;i++){
  78. 			for(llo j=0;j<=26;j++){
  79. 				for(llo k=0;k<26;k++){
  80. 					dp2[j][k]=0;
  81. 				}
  82. 			}
  83. 			for(llo j=1;j<=26;j++){
  84. 				for(llo k=0;k<26;k++){
  85. 					for(llo l=0;l<k;l++){
  86. 						if(l<i and k>i){
  87. 							continue;
  88. 						}
  89. 						dp2[j][k]=max(dp2[j][k],dp2[j-1][l]+ma2[l][k]);
  90. 					}
  91. 				}
  92. 			}
  93. 			for(llo j=0;j<=26 and j<=q;j++){
  94. 				ans=max(ans,dp2[j][25]+(q-j)*ma[i]);
  95. 			}
  96.  
  97. 		}
  98. 		//cout<<ma2[0][3]<<":"<<ma2[3][4]<<endl;
  99. 		cout<<ans<<endl;
  100.  
  101. 	}
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108. 	return 0;
  109. }
Success #stdin #stdout 0.01s 26956KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tBuTPA
language:
C++14 (gcc 8.3)
created:
3 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!