Submission

PPPPPPPPPP

Score: 100

User: Ecir

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-21 14:28:09

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
#define twod array<ll,2>
int dp[609][609];
vector<char> ans;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    string s1,s2;cin >> s1 >> s2;
    int sz=s1.size();
    for(int i=1;i<=sz;i++){
        for(int j=1;j<=sz;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]);
        }
    }
    string ans="";
    int i=s1.size(),j=s2.size();
    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;
    cout << "\n";
    cout << dp[sz][sz] << "\n";
    if(dp[sz][sz]*2>=sz) cout << "y";
    else cout << 'n';

    return 0;
}