Cod sursa(job #1443342)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 27 mai 2015 18:59:51
Problema Cel mai lung subsir comun Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <stack>
#define _submit
#ifdef _submit
#define InFile "cmlsc.in"
#define OutFile "cmlsc.out"
#else
#define InFile "fis.in"
#define OutFile "fis.out"
#endif

#define MAXN 1030

short v1[MAXN], v2[MAXN];
short len[MAXN][MAXN];
short newelem[MAXN][MAXN];

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OutFile, "w", stdout));
	int N, M;
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++)
	for (int j = 0; j < M; j++)
		newelem[i][j] = -1;
	for (int i = 0; i < N; i++)
		scanf("%d", &v1[i]);
	for (int j = 0; j < M; j++)
		scanf("%d", &v2[j]);

	for (int i = 0; i < N; i++)
	for (int j = 0; j < M; j++) {
		if (i == 0 && j == 0)
			len[i][j] = 0;
		else if (i == 0)
			len[i][j] = len[i][j - 1];
		else if (j == 0)
			len[i][j] = len[i - 1][j];
		else
			len[i][j] = std::max(len[i - 1][j], len[i][j - 1]);
		if (v1[i] == v2[j]) {
			len[i][j]++;
			newelem[i][j] = short(v1[i]);
		}
	}

	int c1 = N - 1, c2 = M - 1;
	printf("%d\n", len[c1][c2]);
	std::stack<short> S;
	while (c1 >= 0 && c2 >= 0) {
		if (newelem[c1][c2] != -1)
			S.push(newelem[c1][c2]);
		if (c1 == 0)
			c2--;
		else if (c2 == 0)
			c1--;
		else if (len[c1 - 1][c2] > len[c1][c2-1])
			c1--;
		else
			c2--;
	}
	while (!S.empty()) {
		printf("%u ", S.top());
		S.pop();
	}
	return 0;
}