Submission

Score: 30

User: mantaggez

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-23 18:31:22

#include <bits/stdc++.h>

using namespace std;

const int nx = 605;

string s1, s2;
int dp[nx][nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> s1 >> s2;
    int n = s1.size();
    s1 = " " + s1;
    s2 = " " + s2;
    // dummy

    // dp[i][j] = len of the LCS;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(s1[i] == s2[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
            // cout << dp[i][j] << ' ';
        }
        // cout << '\n';
    }

    int x = n, y = n;
    string ans = "";
    while(x > 0 && y > 0) {
        if(s1[x] == s2[y]) {
            ans += s1[x];
            x--, y--;
        }
        else if(dp[x - 1][y] >= dp[x][y - 1]) {
            x--;
        }
        else y--;
    }

    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
    cout << dp[n][n] << '\n';
    cout << (dp[n][n] > n / 2 ? "y" : "n") << '\n';

    return 0;
}