Cod sursa(job #1439052)

Utilizator MarianMMorosac George Marian MarianM Data 21 mai 2015 12:36:58
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <iterator>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

#define DMAX 1025
#define MOD 1999999973
#define ll long long
#define ull unsigned long long

int N, M;
vector<int> A, B;

int main(){
	int i, j;

	freopen("cmlsc.in", "r", stdin);
	freopen("cmlsc.out", "w", stdout);
	/*freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);*/

	cin >> N >> M;
	vector<vector<int> > cmlsc;
	cmlsc.resize(N + 1);
	for (i = 0; i <= N; i++) cmlsc[i].resize(M + 1);
	
	for (i = 0; i < N; i++) cin >> j, A.push_back(j);
	for (i = 0; i < M; i++) cin >> j, B.push_back(j);

	for (i = 1; i <= N; i++){
		for (j = 1; j <= M; j++){
			if (A[i-1] == B[j-1])
				cmlsc[i][j] = 1 + cmlsc[i][j - 1];
			else
				cmlsc[i][j] = max(cmlsc[i][j - 1], cmlsc[i - 1][j]);
		}
	}

	cout << cmlsc[N][M] << '\n';

	int lg = 0;
	for (i = 1; i <= N; i++){
		for (j = 1; j <= M; j++){
			if (cmlsc[i][j] > lg){
				cout << A[i-1] << ' ';
				lg = cmlsc[i][j];
			}
		}
	}

	return 0;
}