Submission

Score: 100

User: skibididopdop

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-15 16:44:43

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

int main(){
    string s1,s2;
    cin>>s1>>s2;
    int n=s1.size();
    int m=s2.size();
    vector <vector<int>> lcs(n+5,vector <int>(n+5));
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (s1[i-1]==s2[j-1]){
                lcs[i][j]=lcs[i-1][j-1]+1;
            }
            else {
                lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
            }
        }
    }
    int x=n;
    int y=m;
    string ans;
    while (x>0&&y>0){
        if (s1[x-1]==s2[y-1]){
            ans.push_back(s1[x-1]);
            x--;
            y--;
        }
        else if (lcs[x-1][y]>lcs[x][y-1]){
            x--;
        }
        else {
            y--;
        }
    }
    for (int i=ans.size()-1;i>=0;i--){
        cout<<ans[i];
    }
    cout<<"\n";
    cout<<ans.size()<<"\n";
    if (ans.size()>n/2){
        cout<<"y";
    }
    else {
        cout<<"n";
    }
}