Cod sursa(job #2737106)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 4 aprilie 2021 14:07:54
Problema Cel mai lung subsir comun Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << "\n";

ifstream in("cmlsc.in");
ofstream out("cmlsc.out");

const int max_n = (int)2e3 + 5;

int n, m;

int a[max_n], b[max_n];

int dp[max_n][max_n];

int ans[max_n];

int main() {
  in >> n >> m;
  for (int i = 1; i <= n; i++) {
    in >> a[i];
  }
  for (int j = 1; j <= m; j++) {
    in >> b[j];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (a[i] == b[j]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  out << dp[n][m] << "\n";
  int i = n, j = m;
  vector<int> ans;
  while (i > 0 && j > 0) {
    if (dp[i][j] == 1 + dp[i - 1][j]) {
      ans.push_back(a[i]);
      i--;
    } else if (dp[i][j] == 1 + dp[i][j - 1]) {
      ans.push_back(b[j]);
      j--;
    } else {
      i--;
      j--;
    }
  }
  reverse(ans.begin(), ans.end());
  for (int val : ans) {
    out << val << " ";
  }
  return 0;
}