Submission

Score: 100

User: navysrimuang

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.004 second

Submitted On: 2026-03-20 11:31:18

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
	string a,b;
	cin >> a >> b;
	int n = a.size();
	vector<vector<int>> dp(n+2,vector<int>(n+2,0));	

	for(int i = 1;i<=n;i++){
		for(int j = 1;j<=n;j++){
			dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
			if(a[i-1] == b[j-1]){
				dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j]);
			}
		}
	}

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


//	 a a b c

// a 1 1 1 1
// b 1 1 2 1
// c 1 1 2 3
// a 1 2 2 3