Submission

Score: 0

User: devilpoohs

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-08 11:24:14

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

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);2;
    cin>>s1>>s2;
    int n=s1.size();
    memset(dp,0,sizeof(dp));
    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);
            dp[i][j]=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;
}