Submission

PPPPPPPPPP

Score: 100

User: Nozomi_boundfortokyo

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-20 22:17:19

#include <bits/stdc++.h>
using namespace std;
int dp[601][601];
string consider;
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;
			}
			else
			{
				dp[i][j]=dp[i][j-1];
			}
	    }
	    else if(j==0)
	    {
   	 	   	if(s1[i]==s2[j])
   	 	   	{
   	 	   		dp[i][j]=1;
			}
			else
			{
				dp[i][j]=dp[i-1][j];
			}
		}
		else
		{
			if(s1[i]==s2[j])
			{
				dp[i][j]=dp[i-1][j-1]+1;
			}
			else
			{
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
	 }
   }
   int i=s1.size()-1;
   int j=s2.size()-1;
   while(i>=0 && j>=0)
   {
       if(s1[i]==s2[j])
       {
           consider.push_back(s1[i]);
           i--;
           j--;
       }
       else
       {
           if(dp[i-1][j]>dp[i][j-1]) i--;
           else j--;
       }
   }
   reverse(consider.begin(),consider.end());
   cout<<consider<<'\n';
   cout<<consider.size()<<'\n';
   if(consider.size()>0.5*s1.size())
   {
       cout<<"y";
   }
   else cout<<"n";
}