Submission

PPPPPPPPPP

Score: 100

User: Ecir

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.057 second

Submitted On: 2025-03-21 12:58:48

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

    return 0;
}