Cod sursa(job #1817949)

Utilizator KusikaPasa Corneliu Kusika Data 28 noiembrie 2016 18:17:47
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.56 kb
#include <iostream>
#define N 1<<10
using namespace std;
short i,j,d[N][N],n,m,a[N],b[N],s[N],r;
int main()
{
    //ifstream cin ("cmlsc.in");
    //ofstream cout ("cmlsc.out");
    cin>>n>>m;
    for(i=1;i<=m;i++) cin>>a[i];
    for(i=1;i<=n;i++) cin>>b[i];
    for(int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) d[i][j]=(a[i]==b[j])?d[i-1][j-1]+1:max(d[i-1][j],d[i][j-1]);
    for(i=m,j=n;i;)
        if(a[i]==b[i]) s[++r]=a[i],i--,j--;
        else (d[i-1][j]<d[i][j-1])?j--:i--;
    cout<<r<<"\n";
    for(i=r;i;i--) cout<<s[i]<<" ";
}