Submission

P--P---P--

Score: 30

User: Nathlol2

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.064 second

Submitted On: 2025-03-15 15:44:33

#include <bits/stdc++.h>
using namespace std;
string a, b;
const int N = 605;
string s[N][N];
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 = 0;i<N;i++){
        for(int j = 0;j<N;j++){
            s[i][j] = "";
        }
    }
    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;
                s[i][j] = s[i - 1][j - 1] + a[i - 1];
            }else if(dp[i - 1][j] >= dp[i][j - 1]){
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                s[i][j] = s[i - 1][j];
            }else{
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                s[i][j] = s[i][j - 1];
            }
        }
    }
    cout << s[n][m] << '\n';
    cout << dp[n][m] << '\n';
    if(dp[n][m] * 2 > n){
        cout << "y\n";
    }else{
        cout << "n\n";
    }
}