fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define all(x) x.begin(), x.end()
  4. #define rall(x) x.rbegin(), x.rend()
  5. #define sz(x) (int)(x).size()
  6.  
  7. using namespace std;
  8. const double pi = acos(-1);
  9. const int mod = 1e9 + 7;
  10. const int N = 1e3 + 5, M = 1e2 + 2, K = 5e2 + 5;
  11.  
  12. int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
  13. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  14.  
  15. void fast()
  16. {
  17. #ifndef ONLINE_JUDGE
  18.     freopen("input.txt", "r", stdin);
  19.     freopen("output.txt", "w", stdout);
  20. #endif
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(nullptr), cout.tie(nullptr);
  23. }
  24.  
  25. int id = 0;
  26. string s;
  27. int dp[N][N], vis[N][N];
  28.  
  29. int lcs(int i, int j)
  30. {
  31.     if (i > j)
  32.         return 0;
  33.  
  34.     if (i == j)
  35.         return 1;
  36.  
  37.     int &ret = dp[i][j];
  38.  
  39.     if (vis[i][j] == id)
  40.         return ret;
  41.  
  42.     if (s[i] == s[j])
  43.         return ret = 2 + lcs(i + 1, j - 1);
  44.  
  45.     ret = 0, vis[i][j] = id;
  46.     ret = max(ret, lcs(i, j - 1));
  47.     ret = max(ret, lcs(i + 1, j));
  48.     return ret;
  49. }
  50.  
  51. int32_t main()
  52. {
  53.     fast();
  54.  
  55.     while (cin >> s)
  56.     {
  57.         id++;
  58.         int x = lcs(0, s.size() - 1);
  59.         cout << x << "\n";
  60.     }
  61.  
  62.     return 0;
  63. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SZe1zW
language:
C++ (gcc 8.3)
created:
3 days 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!