Submission

Score: 100

User: Bune

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-24 20:46:44

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()

int main() {
  fastio

  string a, b;
  cin >> a >> b;

  int aSize = a.size();
  int bSize = b.size();

  vector<vector<int>> dp(aSize + 5, vector<int>(bSize + 5));

  for (int i = 1; i <= a.size(); i++) {
    for (int j = 1; j <= b.size(); 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]);
      }
    }
  }

  string ans;
  int x = aSize;
  int y = bSize;

  while (x > 0 && y > 0) {
    if (a[x-1] == b[y-1]) {
      x--;
      y--;
      ans += a[x];
    }
    else if (dp[x-1][y] > dp[x][y-1]) {
      x--;
    }
    else {
      y--;
    }
  }

  reverse(ans.begin(), ans.end());

  cout << ans << "\n" << dp[a.size()][b.size()] << "\n";

  if (dp[a.size()][b.size()] >= a.size() / 2) {
    cout << "y\n";
  }
  else {
    cout << "n\n";
  }

  return 0;
}