fork 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, t, ans;
  27. int dp[N][N], vis[N][N];
  28.  
  29. int lcs(int i, int j)
  30. {
  31.  
  32.     if (i == s.size() || j == t.size())
  33.         return 0;
  34.  
  35.     int &ret = dp[i][j];
  36.  
  37.     if (vis[i][j] == id)
  38.         return ret;
  39.  
  40.     vis[i][j] = id, ret = 0;
  41.  
  42.     if (s[i] == t[j])
  43.         return ret = 1 + lcs(i + 1, j + 1);
  44.  
  45.     ret = max(ret, lcs(i + 1, j));
  46.     ret = max(ret, lcs(i, j + 1));
  47.     return ret;
  48. }
  49.  
  50. void build(int i, int j)
  51. {
  52.  
  53.     if (i == s.size() || j == t.size())
  54.         return;
  55.  
  56.     if (s[i] == t[j])
  57.     {
  58.         ans += s[i];
  59.         build(i + 1, j + 1);
  60.         return;
  61.     }
  62.  
  63.     if (lcs(i + 1, j) == lcs(i, j + 1))
  64.     {
  65.         if (s[i] >= t[j])
  66.             build(i + 1, j);
  67.         else
  68.             build(i, j + 1);
  69.         return;
  70.     }
  71.  
  72.     if (lcs(i + 1, j) > lcs(i, j + 1))
  73.         build(i + 1, j);
  74.     else
  75.         build(i, j + 1);
  76. }
  77.  
  78. int32_t main()
  79. {
  80.     fast();
  81.  
  82.     while (cin >> s)
  83.     {
  84.         t = s, ans = "";
  85.         reverse(all(t));
  86.         id++;
  87.         int x = lcs(0, 0);
  88.         build(0, 0);
  89.         cout << ans << "\n";
  90.     }
  91.  
  92.     return 0;
  93. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7zcsi3
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!