Submission

PPPPPPPPPP

Score: 100

User: Ongsa123

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.077 second

Submitted On: 2025-03-21 13:57:13

#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;
                from[i][j] = from[i-1][j-1];
                from[i][j].push_back(s1[i-1]);
            }
            else{
                if(dp[i-1][j] > dp[i][j-1]){
                    dp[i][j] = dp[i-1][j];
                    from[i][j] = from[i-1][j];
                }
                else{
                    dp[i][j] = dp[i][j-1];
                    from[i][j] = from[i][j-1];
                }
            }
        } 
    }
    int siz = from[len][len].size();
    for(int i=0;i<siz;i++){
        cout << from[len][len][i];
    }
    cout  << "\n" << dp[len][len] << "\n" << (siz*2 > len ? 'y' : 'n');
    return 0;
}