Submission

PPPPPPPPPP

Score: 100

User: YoruoniVamp

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.072 second

Submitted On: 2025-03-13 12:31:39

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ld long double
#define ull unsigned ll
#define cint const int
#define cf const float

cint mxA = 1e6+5, MOD = 1e9+7, INF = 0x3f3f3f3f;
cint d4x[4] = {0, 1, 0, -1}, d4y[4] = {1, 0, -1, 0};
cint d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

int dp[605][605];
string dps[605][605], s1, s2;

void solve(){
    for(int i = 0; i < 605; i++) for(int j = 0; j < 605; j++) dps[i][j] = "";
    cin >> s1 >> s2;
    for(int i = 1; i <= s1.length(); i++){
        for(int j = 1; j <= s2.length(); j++){
            if(s1[i-1]==s2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
                dps[i][j] = dps[i-1][j-1] + s1[i-1];
            }else{
                if(dp[i][j-1]>dp[i][j]){
                    dp[i][j] = dp[i][j-1];
                    dps[i][j] = dps[i][j-1];
                }if(dp[i-1][j]>dp[i][j]){
                    dp[i][j] = dp[i-1][j];
                    dps[i][j] = dps[i-1][j];
                }
            }
        }
    }
    // cout << "DPED" << endl;
    // for(int i = 1; i <= s1.length(); i++){
    //     for(int j = 1; j <= s2.length(); j++) cout << dps[i][j] << ' ';
    //     cout << endl;
    // }
    cout << dps[s1.length()][s2.length()] << endl;
    cout << dps[s1.length()][s2.length()].length() << endl;
    if(dps[s1.length()][s2.length()].length()>=(s1.length()+1)/2) cout << 'y';
    else cout << 'n';
    return;
}

int main(){
    // cin.tie(nullptr)->sync_with_stdio(0);cout.tie(0);
    // freopen("", "r", stdin);
    // freopen("", "w", stdout);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}