fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ll fun1(string a,string b){
  5. int a1=a.length()-1;
  6. int b1=b.length()-1;
  7. ll ans=0;
  8. while(a1>=0 && b1>=0 && a[a1]==b[b1]){a1--; b1--; ans++;}
  9. return ans;
  10. }
  11. ll fun2(string a,string b){
  12. int a1=0;
  13. int b1=0;
  14. ll ans=0;
  15. while(a1<a.length() && b1<b.length()&& a[a1]==b[b1]){ans++; a1++; b1++;}
  16. return ans;
  17. }
  18. ll fun(string a,string b){
  19. ll temp=min(fun1(a,b),fun2(a,b));
  20. return (temp*temp);
  21. }
  22.  
  23. int main(){
  24. int t;
  25. scanf("%d",&t);
  26. while(t--){
  27.     int n;
  28.     scanf("%d",&n);
  29.     string a[n];
  30.     for(int i=0;i<n;i++)cin>>a[i];
  31.     if(n==1){cout<<"0"<<endl; continue;}
  32.     else if(n==2){cout<<fun(a[0],a[1])<<endl; continue;}
  33.  
  34.  
  35.     sort(a,a+n);
  36.     map<ll,ll> map1;
  37.      for(int i=1;i<n;i++){
  38.         ll temp=fun(a[i-1],a[i]);
  39.       map1[i]=temp;
  40.     }
  41.     string look[n];
  42.     look[0]=a[0];
  43.     ll cost[n];
  44.     cost[0]=0;
  45.     cost[1]=map1[1];
  46.     look[1]="";
  47.     for(int i=2;i<n;i++){
  48.     string tt=look[i-1];
  49.     if(tt==""){
  50.  
  51.         ll t1=cost[i-2]+map1[i];
  52.         if(t1>cost[i-1]){
  53.             cost[i]=t1;
  54.             look[i]=look[i-2];
  55.         }
  56.         else{
  57.             cost[i]=cost[i-1];
  58.           look[i]=a[i];
  59.         }
  60.  
  61.     }
  62.    else{
  63.       if(tt==a[i-1]){
  64.         cost[i]=cost[i-1]+map1[i];
  65.       }
  66.       else{
  67.         ll t1=cost[i-1]+fun(a[i],tt);
  68.         ll t2=cost[i-2]+map1[i];
  69.          cost[i]=max(t1,t2);
  70.  
  71.       }
  72.      look[i]="";
  73.    }
  74.  
  75.     }
  76.  
  77.   cout<<cost[n-1]<<endl;
  78.  
  79.  
  80. }
  81.  
  82.  
  83. return 0;
  84. }
Success #stdin #stdout 0s 4340KB
comments (?)
stdin
copy 
1
3
abca
acd
ada
stdout
copy 
0
https://ideone.com/6IzOIl
language:
C++14 (gcc 8.3)
created:
4 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!