Cod sursa(job #3238333)

Utilizator Spikyscutaru matei Spiky Data 24 iulie 2024 11:57:24
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>

using namespace std;

ifstream cin("cmlsc.in");
ofstream cout("cmlsc.out");

int n, m, v[1025][1025], a[1025], b[1025], sol[1025], cnt;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int j=1;j<=m;j++)
        cin>>b[j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i]==b[j])
                v[i][j]=1+v[i-1][j-1];
            else
                v[i][j]=max(v[i-1][j],v[i][j-1]);
    for(int i=n,j=m;i>=1;)
    {
        if(v[i][j]== v[i-1][j-1]+1)
        {
            sol[++cnt]=a[i];
            i--;
            j--;
        }
        else if(v[i][j-1]>v[i-1][j])
        j--;
        else
            i--;
    }
    for(int i=cnt;i>=1;i--)
        cout<<sol[i]<<" ";
}