Cod sursa(job #2208212)

Utilizator IamNeganradu radu IamNegan Data 28 mai 2018 18:10:35
Problema Cel mai lung subsir comun Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cmath>
#include <cstdio>
#include <map>
#include <assert.h>
#include <cassert>
#include <iomanip>
#include <set>
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

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

int max(int a, int b) { return a > b ? a : b; }
int N, M, arr1[2025], arr2[2025], matrix[2025][2025], seq[2025];
int main() {
	fin >> N >> M;
	for (int i = 0; i < N; i++) {
		fin >> arr1[i];
	}
	for (int i = 0; i < M; i++) {
		fin >> arr2[i];
	}

	int index = 0;
	for (int row = 0; row <= N; ++row) {
		for (int col = 0; col <= M; ++col)
		{
			if (row == 0 || col == 0)
				matrix[row][col] = 0;
			else if (arr1[row - 1] == arr2[col - 1]) {
				matrix[row][col] = 1 + matrix[row - 1][col - 1];
				seq[index++] = arr1[row - 1];
			}
			else
				matrix[row][col] = max(matrix[row - 1][col], matrix[row][col - 1]);
		}
	}
	fout << matrix[N][M];

	fout << "\n";
	for (int i = 0; i < matrix[N][M]; i++) {
		fout << seq[i] << " ";
	}

	return 0;

}