fork download
copy 
  1. /*
  2. TASK: XNP
  3. LANG: C++
  4. */
  5. #include<bits/stdc++.h>
  6. #define int long long
  7. #define f1(i, n) for(int i=1;i<=n;++i)
  8. #define all(x) x.begin(), x.end()
  9. #define fi first_min
  10. #define se second
  11. #define pb push_back
  12. #define endl "\n"
  13. #define NAME "XNP"
  14. using namespace std;
  15. const int maxn = 1e5 + 5;
  16. const int INF = 1e18;
  17.  
  18. int dp[3005][3636];
  19.  
  20.  
  21. int32_t main() {
  22.     ios::sync_with_stdio(false);
  23.     cin.tie(nullptr);
  24.     cout.tie(nullptr);
  25.  
  26.     if (fopen(NAME".INP", "r")) {
  27.         freopen(NAME".INP", "r", stdin);
  28.         freopen(NAME".OUT", "w", stdout);
  29.     }
  30.  
  31.     string s, t;
  32.     cin >> s;
  33.     t = s;
  34.     reverse(all(s));
  35.     int a = s.size(), b = t.size();
  36.     // s = " " + s;
  37.     // t = " " + t;
  38.     for (int i = 1; i <= a; ++i) {
  39.         for (int j = 1; j <= b; ++j) {
  40.             if (s[i - 1] == t[j - 1]) {
  41.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  42.             }
  43.             else {
  44.                 dp[i][j] = max({dp[i - 1][j], dp[i][j - 1]});
  45.             }
  46.         }
  47.     }
  48.  
  49.     int temp = dp[a][b];
  50.     string res = "";
  51.  
  52.     for (int i = a; i >= 1; --i) {
  53.         for (int j = b; j >= 1; --j) {
  54.             if (temp == dp[i][j] && s[i - 1] == t[j - 1]) {
  55.                 res += s[i - 1];
  56.                 temp--;
  57.                 break;
  58.             }
  59.             // cout << dp[i][j] << " ";
  60.         }
  61.         // cout << endl;
  62.     }
  63.  
  64.     reverse(all(res));
  65.     cout << res;
  66.     // cout<<res.size();
  67.  
  68.  
  69.  
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HzGNtB
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!