Cod sursa(job #2776989)

Utilizator francescom_481francesco martinut francescom_481 Data 21 septembrie 2021 19:15:12
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include<bits/stdc++.h>

using namespace std;

ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
#define cin fin
#define cout fout

#define N 1030
int n, m, nr, v[N], w[N], s[N], d[N][N];

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> v[i];
    }
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> w[i];
    }
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            if(v[i] == w[j])
            {
                d[i][j] = d[i-1][j-1]+1;
            }
            else d[i][j] = max(d[i-1][j],d[i][j-1]);
        }
    }
    for(int i = n, j = m ; i ;)
    {
        if(v[i] == w[j])
        {
            s[++nr] = v[i];
            i--, j--;
        }
        else if(d[i-1][j] < d[i][j-1])j--;
        else i--;
    }
    cout << nr << '\n';
    for(int i =nr ; i ; i--)
    {
        cout << s[i] << ' ';
    }
    cout << d[n][m] << '\n';
    return 0;
}