Submission

Score: 100

User: Chawin

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-15 22:28:13

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

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    string s1, s2;
    cin >> s1;
    cin >> s2;

    int n = s1.size();
    int m = s2.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(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 a = "";
    while(x != 0 && y != 0){
        if(s1[x-1] == s2[y-1]){
            a += s1[x-1];
            x--;
            y--;
        }
        else if(dp[x-1][y] > dp[x][y-1]){
            x--;
        }
        else{
            y--;
        }
    }

    for(int i = a.size()-1; i >= 0; i--){
        cout << a[i];
    }
    cout << "\n";

    cout << dp[n][m] << "\n";

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

    return 0;
}