fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. /*
  6.  * Complete the 'playWithWords' function below.
  7.  *
  8.  * The function is expected to return an INTEGER.
  9.  * The function accepts STRING s as parameter.
  10.  */
  11.  
  12. short dp[3010][3010];
  13.  
  14. int solve(int i, int j, string s)
  15. {
  16.     // cout << i << ' ' << j << endl;
  17.     if (i > j)
  18.         return 0;
  19.     if (dp[i][j] != -1)
  20.         return dp[i][j];
  21.     int ans = 0;
  22.     if (s[i] == s[j])
  23.         ans = 2 + solve(i+1, j-1, s);
  24.     // else
  25.     // {
  26.     ans = max(ans, solve(i+1, j, s));
  27.     ans = max(ans, solve(i, j-1, s));
  28.     // }
  29.     return dp[i][j] = ans;
  30. }
  31.  
  32. int playWithWords(string s) {
  33.     memset(dp, -1, sizeof(dp));
  34.     for (int i=0; i<s.length(); i++)
  35.         dp[i][i] = 1;
  36.     solve(0, s.length()-1, s);
  37.     int ans = 1;
  38.     for (int i=0; i<s.length(); i++)
  39.         ans = max(ans, dp[0][i]*dp[i+1][s.length()-1]);
  40.     return ans;
  41. }
  42.  
  43. int main()
  44. {
  45.     // ofstream fout(getenv("OUTPUT_PATH"));
  46.  
  47.     string s;
  48.     getline(cin, s);
  49.  
  50.     int result = playWithWords(s);
  51.  
  52.     cout << result << "\n";
  53.  
  54.     return 0;
  55. }
  56.  
Success #stdin #stdout 2.64s 25208KB
comments (?)
stdin
copy 
abbbaaabaabaabbaaaaaabbabababbaaabbbbaabbbbbaabbabbaabbbbbaaabaaabbaabaabbabababbbaabababbabbaaaabbbababaabababababaabbbabaabbbaabbbaabbabbaabbbbbabaaabbaabbaaababbbbbbabaaabbbbbbbbbaabbabbbaabbbaaaaabaaabbbababbabaabbbabbabababaabbbbabbababbaabaaaabbabbabaaaaabbaabbbbbbaabababbbbabababbbaaababbaabbbabababaaabaaabbaaababababbbabaaaababaaabbaabaabbaabbaabaaaabaaabaababaabaababbbabaaabbabaababaabaababaaaaabbbbbaabaaabbbbababaabbbbbbbbababaaababaababaabbbaabbaaabaabbbaababaaabbbabbbababaabbababaaaaaaabbbbbbbabbbbbbababbbbbabbbbbbbabbbbabbbbabbbabaaaaaaaabbabbbababaaaaaabababaaaaabbaaabaabbbaabbbbbababbbbbaaaababbbabbabbaabaabbabbbabbbaabaabbaabbaabbbbaaabbbaaabaaababaaabbaabbabbaabbbbaabbabaaaabaabbabaaababbbbaabbaabaababaabbabbbaaabbabaabaabbbbbbababbaababbaabaaaabbabbaaaaabababbaabbaabababbbaabbbabbabbbbaaabaaabbaabaaabaabbbbbaabbbabbbbbbaaaabbbabbbabbaabababbabbaaaaaaaaaabaababaabaaaaaaababaaaabbaabaabbbbbabbbbbaabbaabbababaabbaaaababaabaaabaabbbbbaabbbababbababaaaaabbbaabbabababbabaaabbaaaabaababbabaaabaababaabaaaabbbaaabbbbbbbbbaababaabababbbbaabaabbaabbbababbbbabaaabbaaabbababbabababbbaaabbabaaaabaababbbaabbaabababbbaaabbaaabbabaabaabaaabbbaaabbaabbaaaaabbabaabbbbbabbabbabbbbbababaaaaababaabbbababbbbabbbaaaabbbbbbbbbbbaabbaabbaaaaaaaaaabbbbaababaabbabaaaabbaabbaabbaababbbaabbbabbbabbabbbbaabbbbbbbbbbbbababbaaabaabbbabbbbbaababababbabbbbaabaaabbaaabbabbaabaaaaaabbbabaaaabaabbbabbaabbaaabbaaaaabbbbababbaabbaabababaabbbbbbababaabbbaaabaabababbabbabbbbabbababbabbbabbbbbaabbabaababaaabbabbbabaaabaabaaabaababaabaabbbbabbaaabbaaabbbaaabbaaaabbbaaaabaabbabbbaaabaabaaaaaaababbbaabbabaabaaaababbbbbbabbbaaaabaabbabbbaabbaababbbbbbbababbaaabbaaaaabbbbaaaabbaaaaaaaaaaaabbbbabbaabbabbabbbbbaaabaabbaabbbaabbbbbbbaabbbababaaaaaabbbaabbaaabaabbbabaabaabbbbbaaaaaabaaaabbaaabbaaabaaaaaaaaabbbaaababbbbabbbbababbaaabbabaababaabaabbaaaaababbaabbbbbbbaababbbabbaabbaabaabbabababaabaabababaabbbbbabbbabbaabbaaabaaaaabaabbbbaabbbbbbbbbabbbbabbbbbbbababbbabaaaaabababaababaabbbabbabbbaabbaab
stdout
copy 
664858
https://ideone.com/QT46Wc
language:
C++ (gcc 8.3)
created:
3 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!