Submission

PPPPPPPPPP

Score: 100

User: Nathlol2

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.003 second

Submitted On: 2025-03-15 15:56:05

#include <bits/stdc++.h>
using namespace std;
const int N = 605;
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    string a, b;
    cin >> a >> b;
    int n = a.size();

    vector<vector<int>> dp(N, vector<int>(N, 0));

    string ans = "";
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(a[i - 1] == b[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    int i = n, j = n;
    while(i > 0 && j > 0){
        if(a[i - 1] == b[j - 1]){
            ans += a[i - 1];
            i--;
            j--;
        }else if(dp[i - 1][j] > dp[i][j - 1]){
            i--;
        }else{
            j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
    cout << dp[n][n] << '\n';
    if(dp[n][n] > n/2){
        cout << "y";
    }else{
        cout << "n";
    }
    cout << '\n';
}