Submission

P--P---P--

Score: 30

User: Nathlol2

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.004 second

Submitted On: 2025-03-15 15:40:06

#include <bits/stdc++.h>
using namespace std;
string a, b;
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> a >> b;
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(a[i - 1] == b[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    string ans = "";
    int i = n, j = m;
    while(i > 0 && j > 0){
        if(a[i - 1] == b[j - 1]){
            ans += a[i - 1];
            i--;
            j--;
        }else if(dp[i - 1][j] >= dp[i][j - 1]){
            i--;
        }else{
            j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
    cout << dp[n][m] << '\n';
    if(dp[n][m] * 2 > n){
        cout << "y\n";
    }else{
        cout << "n\n";
    }
}