Submission

Score: 0

User: devilpoohs

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-08 08:38:27

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int dp[602][602];
#define think(i,j) dp[i][j]
bool chk=false;
#define int long long
void gon(int i,int j){
    if(i==0 or j==0){
        chk=true;
        return ;
    }else if(dp[i-1][j-1]==dp[i][j] and !chk) gon(i-1,j-1);
    else if(dp[i-1][j]==dp[i][j] and !chk) gon(i-1,j);
    else if(dp[i][j-1]==dp[i][j] and !chk) gon(i,j-1);
    else if(dp[i][j]==1+think(i-1,j-1) and !chk){
        gon(i-1,j-1);
           cout<<s2[j-1];
    }
    
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);2;
    cin>>s1>>s2;
    int n=s1.size();
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(i==0 or j==0) dp[i][j]=0;
            else if(s1[i-1]==s2[j-1]) dp[i][j]=1+think(i-1,j-1);
            else dp[i][j]=max(think(i-1,j-1),max(think(i-1,j),think(i,j-1)));
        }
    }
    gon(n,n);
    cout<<'\n'<<think(n,n)<<'\n';
    if(think(n,n)<=n/2) cout<<"y";
    else cout<<"n";
    return 0;
}