Submission

Score: 100

User: kenmuay

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-15 22:27:20

#include <bits/stdc++.h>
using namespace std;



int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    string s1, s2;
    cin >> s1 >> s2;
    
    int n = s1.length(), m = s2.length();
    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(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 x=n, y=m;
    string ans = "";
    while(x != 0 && y != 0){
        if(s1[x-1] == s2[y-1]) {ans+=s1[x-1]; x--, y--;}
        else if(dp[x-1][y] > dp[x][y-1]) x--;
        else y--;
    }

    reverse(ans.begin(), ans.end());
    cout << ans << '\n' << dp[n][m] << '\n';

    if(dp[n][m] > n/2) cout << "y";
    else cout << "n";
    
}