Submission

PPPPPPPPP-

Score: 90

User: Nozomi_boundfortokyo

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.216 second

Submitted On: 2025-03-20 22:03:39

#include <bits/stdc++.h>
using namespace std;
int dp[601][601];
string consider[601][601];
string s1,s2;
int main()
{
   cin>>s1>>s2;
   for(int i=0;i<s1.size();i++)
   {
   	 for(int j=0;j<s2.size();j++)
   	 {
   	 	if(i==0)
   	 	{
   	 	   	if(s1[i]==s2[j])
   	 	   	{
   	 	   		dp[i][j]=1;
   	 	   		consider[i][j]=s1[i];
			}
			else
			{
				dp[i][j]=dp[i][j-1];
				consider[i][j]=consider[i][j-1];
			}
	    }
	    else if(j==0)
	    {
   	 	   	if(s1[i]==s2[j])
   	 	   	{
   	 	   		dp[i][j]=1;
   	 	   		consider[i][j]=s1[i];
			}
			else
			{
				dp[i][j]=dp[i-1][j];
				consider[i][j]=consider[i-1][j];
			}
		}
		else
		{
			if(s1[i]==s2[j])
			{
				dp[i][j]=dp[i-1][j-1]+1;
				consider[i][j]=consider[i-1][j-1];
				consider[i][j].push_back(s1[i]);
			}
			else if(dp[i-1][j]>dp[i][j-1])
			{
				dp[i][j]=dp[i-1][j];
				consider[i][j]=consider[i-1][j];
			}
			else
			{
				dp[i][j]=dp[i][j-1];
				consider[i][j]=consider[i][j-1];
			}
		}
	 }
   }
   cout<<consider[s1.size()-1][s2.size()-1]<<'\n';
   cout<<consider[s1.size()-1][s2.size()-1].size()<<'\n';
   if(consider[s1.size()-1][s2.size()-1].size()>0.5*s1.size())
   {
       cout<<"y";
   }
   else cout<<"n";
}