Submission

PPPPPPPPPP

Score: 100

User: Ongsa123

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.005 second

Submitted On: 2025-03-21 14:51:04

#include<bits/stdc++.h>
using namespace std;
//vector<char> from[605][605];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    string s1,s2; cin >> s1 >> s2;
    int len = s1.length();
    vector<vector<int>> dp(len+1,vector<int>(len+1,0));
    for(int i=1;i<=len;i++){
        for(int j=1;j<=len;j++){
            if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = max(dp[i][j-1],dp[i-1][j]) ;
        } 
    }
    string ans = "";
    int i = len;
    int j = len;
    while(i > 0 && j > 0){
        if(s1[i-1] == s2[j-1]){
            ans += s1[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" << dp[len][len] << "\n" << (dp[len][len]*2 > len ? 'y' : 'n');
    return 0;
}