Submission

P--P---P--

Score: 30

User: krittaphot

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.005 second

Submitted On: 2025-03-15 11:48:10

#include <bits/stdc++.h>

using namespace std;

int main()
{
    string s1,s2;
    cin >> s1 >> s2;
    int n = s1.size();
    int m = s2.size();
    vector<vector<int>> dp(m+1,vector<int> (n+1,0));

    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1]+1;
            else
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
    }
    int ans = dp[n][n];

    stack<char> s;
    int i = n;
    int j = m;
    while(i > 0 && j > 0){
        if(s1[i-1] == s2[j-1]){
            s.push(s1[i-1]);
            i -= 1;
            j -= 1;
        }
        else{
            if(dp[i][j] == dp[i-1][j]){
                i-= 1;
            }
            else if(dp[i][j] == dp[i][j-1]){
                j -=1;
            }
        }
    }

    while(!s.empty()){
        cout << s.top();
        s.pop();
    }
    cout << "\n" << ans << "\n";
    if(ans >= n/2){
        cout << "y";
    }
    else
        cout << "n";
}