Cod sursa(job #2737175)

Utilizator SlavicGGuzun Veaceslav SlavicG Data 4 aprilie 2021 14:52:12
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include "bits/stdc++.h"

using namespace std;
 
#define              ll              int
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
#define         fastio               ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define      GR(a,n,m)               vector<vector<int>> a(n, vector<int>(m, 0));

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

#define cin fin
#define cout fout
const int N = 1100;
int dp[N][N];
void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> a(n), b(m);
	for(int i = 0;i < n;i++){
		cin >> a[i];
	}

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

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

	int i = n, j = m;
	vector<int> v;

	while(i&&j)
	{
		if(a[i-1] == b[j-1]){
			v.pb(a[i-1]);
			--i,--j;
		}else if(dp[i-1][j] >= dp[i][j-1]){
			--i;
		}else{
			--j;
		}
	}


	if(sz(v))reverse(all(v));

	for(int i : v)
		cout << i << " ";

}
 
int32_t main()
{
	//fastio;
    int t = 1;
   	//cin >> t;
   	while(t--)
   	{
   		solve();
   	}
}