Cod sursa(job #2386392)

Utilizator S_AndyAndrei S S_Andy Data 22 martie 2019 18:54:33
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>



using namespace std;



ifstream fin("cmlsc.in");

ofstream fout("cmlsc.out");



int main()

{

	int n, m, *a, b, *ab, *c, max_ab, i, j;

	fin >> n >> m;

	a = new int[n + 1];

	ab = new int[(n + 1) * (m + 1)];

	ab[0] = 0;

	for (i = 1; i <= n; ++i) {

		fin >> a[i];

		ab[i*(m + 1)] = 0;

	}

	for (j = 1; j <= m; ++j) {

		ab[j] = 0;

		fin >> b;

		for (i = 1; i <= n; ++i) {

			(b == a[i]) ? (ab[i*(m + 1) + j] = ab[(i - 1)*(m + 1) + j - 1] + 1) : (ab[i*(m + 1) + j] = max(ab[(i - 1)*(m + 1) + j], ab[i*(m + 1) + j - 1]));

		}

	}



	max_ab = ab[(m + 1)*(n + 1) - 1];

	fout << max_ab << "\n";



	c = new int[max_ab];

	i = n;

	j = m;

	while (max_ab) {

		if (ab[i*(m + 1) + j] > ab[(i - 1)*(m + 1) + j] && ab[i*(m + 1) + j] > ab[i*(m + 1) + j - 1] && ab[i*(m + 1) + j] > ab[(i - 1)*(m + 1) + j - 1]) {

			c[--max_ab] = a[i];

			--i;

			--j;

		}

		else if (ab[i*(m + 1) + j - 1] > ab[(i - 1)*(m + 1) + j]) {

			--j;

		}

		else {

			--i;

		}

	}

	for (i = 0; i < ab[(m + 1)*(n + 1) - 1]; ++i) {

		fout << c[i] << " ";

	}



}