Cod sursa(job #2316281)

Utilizator iugastefanIuga Stefan iugastefan Data 11 ianuarie 2019 15:24:46
Problema Cel mai lung subsir comun Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  ifstream f("cmlsc.in");
  ofstream v("cmlsc.out");
  int n, m;
  f >> n >> m;
  vector<vector<int>> matrice(n + 1, vector<int>(m + 1));
  vector<int> sir1(n + 1), sir2(m + 1);
  for (auto i = 1; i < n + 1; i++)
    f >> sir1[i];
  for (auto i = 1; i < m + 1; i++)
    f >> sir2[i];
  for (auto x = 1; x < n + 1; x++) {
    for (auto y = 1; y < m + 1; y++) {
      matrice[x][y] = max(matrice[x - 1][y], matrice[x][y - 1]);
      if (sir1[x] == sir2[y])
        matrice[x][y] = matrice[x - 1][y - 1] + 1;
    }
  }
  int i = 1;
  vector<int> raspuns;
  for (auto x = 1; x < n + 1; x++) {
    for (auto y = 1; y < m + 1; y++) {
      if (matrice[x][y] >= i) {
        if (matrice[x - 1][y] > matrice[x][y - 1])
          raspuns.push_back(sir1[y]);
        else
          raspuns.push_back(sir1[x]);
        i++;
      }
    }
  }
  v << raspuns.size() << endl;
  for (auto x : raspuns)
    v << x << " ";
}