Submission

Score: 100

User: faofao

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-15 20:47:22

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN = 606 ;
ll dp[mxN][mxN] ;

int main(){
    ios::sync_with_stdio(0),cin.tie(0) ;
    string s1,s2 ; cin >> s1 >> s2 ;
    int n = s1.length() ;
    vector<char> v1(n+1,0) ;
    vector<char> v2(n+1,0) ;
    for(int i=1 ; i<=n ; i++){
        v1[i] = s1[i-1] ;
        v2[i] = s2[i-1] ;
    }

    for(int i=1 ; i<=n ; i++){
        for(int j=1 ; j<=n ; j++){
            if(v1[i] == v2[j]) dp[i][j] = dp[i-1][j-1] +1;
            else dp[i][j] = max(dp[i][j-1] , dp[i-1][j]) ;
        }
    }
    
    int i=n ,j=n;
    vector<char> ans ;
    while(i>0 && j>0){
        if(v1[i] == v2[j]){
            ans.push_back(v1[i]) ;
            i--;
            j--;
        }
        else if(dp[i-1][j] > dp[i][j-1]) i--;
        else j-- ;
    }
    reverse(ans.begin(),ans.end()) ;
    for(auto kv : ans) cout << kv ;
    cout << "\n" ;
    cout <<dp[n][n]<<"\n" ;
    if(ans.size()>n/2) cout << "y" ;
    else cout << "n" ;
}