fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #define ll long long
  4. #define ld long double
  5. #define Marwan  ios::sync_with_stdio(false);cin.tie(nullptr);
  6. #define all(dq)  dq.begin(),dq.end()
  7. using namespace std;
  8. const ll mod = 1000000007;
  9. void pre(){
  10.     Marwan
  11. #ifndef ONLINE_JUDGE
  12.     freopen("input.txt", "r", stdin);
  13.     freopen("output.txt", "w", stdout);
  14. #endif
  15. }
  16. const int N=1005;
  17. int dp[N][N];
  18. string a;
  19. int rec(int i=0,int j=a.size()-1) {
  20.     if(i==j)return 1;
  21.     if (i>j)return 0;
  22.     if (dp[i][j]!=-1)return dp[i][j];
  23.     int ch1=0;
  24.     if (a[i]==a[j])ch1=rec(i+1,j-1)+2;
  25.     int ch2=max(rec(i+1,j),rec(i,j-1));
  26.     return dp[i][j]=max(ch1,ch2);
  27. }
  28. string c;
  29. map<pair<int,int>,string>m;
  30. string bild(int i=0,int j=a.size()-1,string s1="",string s2="") {
  31.     if (j<i)return c=s1+s2;
  32.     if (i==j)return  c=s1+a[i]+s2;
  33.     pair<int,int>ind={i,j};
  34.     if (m.count(ind))return m[ind];
  35.     if (rec(i,j)==rec(i+1,j-1)+2 and a[i]==a[j]) {
  36.         return m[ind]=bild(i+1,j-1,s1+a[i],a[i]+s2);
  37.     }
  38.     if (rec(i,j)==rec(i,j-1) and rec(i+1,j)==rec(i,j-1)) {
  39.         string ch1=bild(i+1,j,s1,s2),ch2=bild(i,j-1,s1,s2);
  40.         return m[ind]=min(ch2,ch1);
  41.     }
  42.     if (rec(i,j)==rec(i+1,j)) {
  43.         return m[ind]=bild(i+1,j,s1,s2);
  44.     }
  45.     if (rec(i,j)==rec(i,j-1)) {
  46.         return  m[ind]=bild(i,j-1,s1,s2);
  47.     }
  48. }
  49. void solve() {
  50.     bool is = false;
  51.     while (cin>>a) {
  52.         if (is) cout << '\n';
  53.         is = true;
  54.         memset(dp,-1,sizeof dp);
  55.         m.clear();
  56.         cout<<bild(0,a.size()-1,"","");
  57.     }
  58. }
  59. int main(){
  60.     pre();
  61.     int t=1;//cin>>t;
  62.     while (t--){
  63.         solve();
  64.     }
  65.     return 0;
  66. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9HpBGf
language:
C++ (gcc 8.3)
created:
7 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!