fork download
copy 
  1. /*
  2.     Cred : SunnyYeahBoi
  3.     It's my last chance (⌐■_■)
  4.     Problem :
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12. #define double long double
  13. #define endl "\n"
  14. #define NAME "a"
  15.  
  16. const int MAXN = 2e3 + 5;
  17. const int inf = 1e18;
  18. const int MOD = 1e9 + 7;
  19.  
  20. void FileInput(){
  21.     if(fopen(NAME".inp" , "r") == NULL)
  22.         freopen(NAME".inp" , "w" , stdout);
  23.     freopen(NAME".inp" , "r" , stdin);
  24.     freopen(NAME".out" , "w" , stdout);
  25. }
  26.  
  27. int n;
  28. string s;
  29. int dp[MAXN][MAXN];
  30.  
  31. string trace(int L , int R){
  32.     if(L > R) return "";
  33.  
  34.     if(s[L] == s[R]){
  35.         if(L == R){
  36.             string t = "";
  37.             t += s[L];
  38.             return t;
  39.         }
  40.         string t = trace(L + 1 , R - 1);
  41.         return s[L] + t + s[R];
  42.     }
  43.  
  44.     if(dp[L + 1][R] > dp[L][R - 1]) 
  45.         return trace(L + 1 , R);
  46.     return trace(L , R - 1);
  47. }
  48.  
  49. void solve(){
  50.     cin >> s;
  51.     n = s.size();
  52.     s = '*' + s;
  53.  
  54.  
  55.     for(int len = 1 ; len <= n ; len++){
  56.         for(int L = 1 ; L + len - 1 <= n ; L++){
  57.             int R = L + len - 1;
  58.             if(R - L + 1 == 1)
  59.                 dp[L][R] = 1;
  60.             else{
  61.                 if(s[L] == s[R])
  62.                     dp[L][R] = dp[L + 1][R - 1] + 2;
  63.                 else dp[L][R] = max(dp[L + 1][R] , dp[L][R - 1]);
  64.             }
  65.         }
  66.     }
  67.  
  68.  
  69.     cout << trace(1 , n) << endl;
  70. }
  71.  
  72. int32_t main(){
  73.     //FileInput();
  74.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  75.     int t = 1;
  76.     // cin >> t;
  77.     while(t--)
  78.         solve();
  79.     return 0;
  80. }
  81.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/9u7UEq
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
24 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!