Submission

Score: 30

User: devilpoohs

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-08 11:10:52

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int dp[602][602];
#define think(i,j) dp[i][j]
bool chk=false;
// #define int long long
vector<char> v;
void gon(int i,int j){
    // cout<<i<<' '<<j<<'\n';
    if(i==0 or j==0){
        // chk=true;
        // strings;
        // string ss="";
        // for(int i=v.size()-1;i>=0;i--){
        //     ss=ss+v[i];
        // }
        // s.insert(ss);
        // cout<<'\n';
        chk=true;
        return ;
    }
    if(dp[i-1][j-1]==dp[i][j] and !chk) gon(i-1,j-1);
    if(dp[i-1][j]==dp[i][j] and !chk) gon(i-1,j);
    if(dp[i][j-1]==dp[i][j] and !chk) gon(i,j-1);

    if(dp[i][j]==1+think(i-1,j-1) and dp[i][j-1]!=dp[i][j] and dp[i-1][j]!=dp[i][j] and dp[i-1][j-1]!=dp[i][j] and !chk){
        // v.emplace_back(s2[j-1]);
        gon(i-1,j-1);
        cout<<s1[i-1];
        // v.pop_back();
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);2;
    cin>>s1>>s2;
    int n=s1.size();
    memset(dp,0,sizeof(dp));
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(i==0 or j==0) dp[i][j]=0;
            else if(s1[i-1]==s2[j-1]) dp[i][j]=1+think(i-1,j-1);
            else dp[i][j]=max(think(i-1,j-1),max(think(i-1,j),think(i,j-1)));
        }
    }
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<=n;j++){
    //         // cout<<dp[i][j]<<','<<s1[i]<<','<<s2[j]<<'|';
    //         cout<<dp[i][j]<<'|';
    //     }
    //     cout<<'\n';
    // }
    gon(n,n);
    // for(auto&i:s){
    //     cout<<i<<'\n';
    // }
    // cout<<s
    cout<<'\n'<<think(n,n)<<'\n';
    if(think(n,n)>n/2) cout<<"y";
    else cout<<"n";
    return 0;
}