Cod sursa(job #2795303)

Utilizator OffuruAndrei Rozmarin Offuru Data 6 noiembrie 2021 10:58:25
Problema Cel mai lung subsir comun Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
#define nmax 1050

using namespace std;

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

int a[nmax],b[nmax],n,m,best[nmax][nmax],sir[nmax];

void read()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    for(int j=1;j<=m;j++)
        fin>>b[j];
}

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

void solve()
{
    dp();
    fout<<best[n][m]<<"\n";
    for(int i=1;i<=best[n][m];i++)
        fout<<sir[i]<<" ";
}

int main()
{
    read();
    solve();
    return 0;
}