Submission

Score: 30

User: C12

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.005 second

Submitted On: 2026-01-07 14:33:36

#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;

void solve(){
    string s1,s2;

    cin >> s1 >> s2;

    vector<vector<pair<uint16_t,pair<uint16_t,uint16_t>>>>dp(s2.length() + 1 , vector<pair<uint16_t,pair<uint16_t,uint16_t>>>(s1.length() + 1));
    // pair<uint16_t,pair<uint16_t,uint16_t>> dp[601][601];

    dp[0][0] = mp(0,mp(0,0));
    dp[1][0] = mp(0,mp(0,0));
    dp[0][1] = mp(0,mp(0,0));

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

    // cout << ' ' << ' ';
    // for(int j = 1;j <= s2.length();j++){
    //     cout << s2[j-1] << ' ';
    // }
    // cout << '\n';
    // for(int i = 1;i <= s1.length();i++){
    //     cout << s1[i-1] << ' ';
    //     for(int j = 1;j <= s2.length();j++){
    //         cout << dp[i][j].f << ' ';
    //     }
    //     cout << '\n';
    // }

    int i = dp[s1.length()][s2.length()].s.f;
    int j = dp[s1.length()][s2.length()].s.s;
    stack<char>st;
    pii t;

    // while(i > 0 && j > 0){
    //     st.push(s1[i]);
    //     t = dp[i][j].s;
    //     i = t.f;
    //     j = t.s;
    // }

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

    // cout << '\n';
    i = s1.length();
    j = s2.length();

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

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

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

    if(dp[s1.length()][s2.length()].f > s1.length()/2 || dp[s1.length()][s2.length()].f > 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
*/