fork download
copy 
  1. /*!enjoy karo yaar!*/
  2.  
  3. //CF,CC,AtC,SPOJ: hp1999
  4. //HE: hemant269
  5. //HR: hemant2132
  6.  
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9.  
  10. #define     int             long long int
  11. #define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  12. #define     all(x)          (x).begin(),(x).end()
  13. #define     rz(x)           resize(x)
  14. #define     asn(x,y)        assign(x,y)
  15. #define     mem(a,b)        memset(a,b,sizeof(a))
  16. #define     sz(x)           ((int)(x.size()))
  17. #define     eb              emplace_back
  18. #define     pb              push_back
  19. #define     pf              push_front
  20. #define     pob             pop_back
  21. #define     pof             pop_front
  22. #define     ins             insert
  23. #define     vi              vector<int>
  24. #define     pii             pair<int,int>
  25. #define     mii             map<int,int>
  26. #define     F               first
  27. #define     S               second
  28. #define     makep           make_pair
  29. #define     maket           make_tuple
  30. #define     remax(a,b)      a=max(a,b)
  31. #define     remin(a,b)      a=min(a,b)
  32. #define     bitcount(x)     __builtin_popcountll(x)
  33. #define     iceil(n,x)      (((n)+(x)-1)/(x))
  34. #define     gcd(a,b)        (__gcd((a),(b)))
  35. #define     lcm(a,b)        (((a)*(b))/gcd((a),(b)))
  36. #define     dbug(x)         cout<<#x<<": "<<(x)<<"\n"
  37. #define     flush           fflush(stdout)
  38. #define     show(x)         for(auto zz:x)cout<<zz<<" ";cout<<"\n";
  39. #define     show2(x)        for(auto zz:x)cout<<zz.F<<" "<<zz.S<<"\n";
  40.  
  41. typedef unsigned long long ull;
  42. typedef long long ll;
  43. typedef long double ld;
  44.  
  45. const ld pi=acos(-1);
  46. const ll inf=1e18,M=1e9+7;
  47. const int N=1e2+5;
  48.  
  49. int dp[N][N][N];
  50.  
  51. string s;
  52. int r1,r2;
  53.  
  54. int rec(int l1,int l2)
  55. {
  56.     if(l1>r1 || l2>r2)
  57.         return 0;
  58.  
  59.     int& res=dp[l1][r1][l2];
  60.     if(res!=-1)
  61.         return res;
  62.  
  63.     res=max({rec(l1+1,l2),rec(l1,l2+1),rec(l1+1,l2+1)+((s[l1]==s[l2])?2:0)});
  64.  
  65.     return res;
  66. }
  67.  
  68. void solve()
  69. {
  70.     mem(dp,-1);
  71.  
  72.     cin>>s;
  73.  
  74.     r2=sz(s)-1;
  75.  
  76.     int ans=0;
  77.     for(int i=0;i+1<=r2;++i)
  78.     {
  79.         r1=i;
  80.         ans=max(ans,rec(0,i+1));
  81.     }
  82.  
  83.     cout<<ans;
  84. }
  85.  
  86. int32_t main()
  87. {
  88.     fast();
  89.  
  90.     int t=1;
  91.     cin>>t;
  92.     for(int z=1;z<=t;++z)
  93.     {
  94.         solve();
  95.         cout<<"\n";
  96.     }
  97.  
  98.     return 0;
  99. }
  100.  
Success #stdin #stdout 0s 12624KB
comments (?)
stdin
copy 
2
aabbaab
aklbjanb
stdout
copy 
6
4
https://ideone.com/fnKhd6
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!