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, ans;
  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. void build(int i, int j)
  52. {
  53.     if (i > j)
  54.         return;
  55.  
  56.     if (i == j)
  57.     {
  58.         ans += s[i];
  59.         return;
  60.     }
  61.     if (s[i] == s[j])
  62.     {
  63.         ans += s[i];
  64.         build(i + 1, j - 1);
  65.         return;
  66.     }
  67.  
  68.     if (lcs(i, j - 1) >= lcs(i + 1, j))
  69.         build(i, j - 1);
  70.     else
  71.         build(i + 1, j);
  72. }
  73.  
  74. int32_t main()
  75. {
  76.     fast();
  77.  
  78.     while (cin >> s)
  79.     {
  80.         id++;
  81.         ans = "";
  82.         int x = lcs(0, s.size() - 1);
  83.         build(0, s.size() - 1);
  84.  
  85.         string temp = ans;
  86.         reverse(all(temp));
  87.  
  88.         if (x % 2 == 1)
  89.             ans.pop_back();
  90.  
  91.         cout << ans << temp << "\n";
  92.     }
  93.  
  94.     return 0;
  95. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GtneUh
language:
C++14 (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!