Submission

Score: 100

User: C12

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.004 second

Submitted On: 2026-01-21 11:05:38

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pii pair<ll,ll>
#define puii pair<ull,ull>
#define piii pair<ll,pii>
#define tiiii tuple<ll,ll,ll,ll>
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define mt make_tuple
 
#define mpiiii(a,b,c) make_pair(a,make_pair(b,c));
// ll mod = 1000000007;
    
ll dp[610][610];

void solve(){
    string s1,s2;

    cin >> s1 >> s2;

    dp[0][0] = 0;
    dp[1][0] = 0;
    dp[0][1] = 0;

    for(int i = 1;i <= s1.length();i++){
        for(int j = 1;j <= s2.length();j++){
            dp[i][j] = 0;
            if(s1[i-1] == s2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            dp[i][j] = max(dp[i][j],dp[i][j-1]);
            dp[i][j] = max(dp[i][j],dp[i-1][j]);
        }
    }

    stack<char>st;
    pii t;
    int i,j;
    i = s1.length();
    j = s2.length();

    while(i > 0 && j > 0){
        if(s1[i-1] == s2[j-1]){            
            st.push(s1[i-1]);
            i--;
            j--;
        }
        else{    
            if(dp[i-1][j] > dp[i][j-1]) i--;
            else j--;
        }
        if(dp[i][j] == 0) break;
    }

    

    while(!st.empty()){
        cout << st.top();
        st.pop();
    }

    cout << '\n';
    cout << dp[s1.length()][s2.length()];
    cout << '\n';

    if(dp[s1.length()][s2.length()] > s1.length()/2 || dp[s1.length()][s2.length()] > s1.length()/2){
        cout << 'y';
    }
    else{
        cout << 'n';
    }
    
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll q;
 
    // cin >> q;

    // while(q--)
        solve(); 

    return 0;
}
/*
oagmmaopsgmorr
ymgaomaaoypnba
*/