Cod sursa(job #3352917)

Utilizator MihaiDraghiciMIHAI DRAGHICI MihaiDraghici Data 2 mai 2026 14:43:46
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
// Doamne ajuta!!!
#include <bits/stdc++.h>
using namespace std;

vector<int> a(1050);
vector<int> b(1050);
vector<vector<int>> com(1050, vector<int>(1050));
vector<int> recons;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

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

	int m;
	int n;

	cin >> m;
	cin >> n;


	for(int i = 1; i <= m; i++){
		cin >> a[i];
	}

	for(int i = 1; i <= n; i++){
		cin >> b[i];
	}

	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(a[j] == b[i]){
				com[i][j] = 1 + com[i - 1][j - 1];
			}
			else{
				com[i][j] = max(com[i - 1][j], com[i][j - 1]);
			}
		}
	}

	cout << com[n][m] << "\n";

	int i = n;
	int j = m;

	while(i > 0 && j > 0){
		if(a[j] == b[i]){
			recons.push_back(a[j]);
			i--;
			j--;
		}
		else{
			if(com[i - 1][j] > com[i][j - 1]){
				i--;
			}
			else{
				j--;
			}
		}
	}

	for(int i = (int)recons.size() - 1; i >= 0; i--){
		cout << recons[i] << " ";
	}

	return 0;
}