Cod sursa(job #2792226)

Utilizator WtfIsThisNeagu Andrei WtfIsThis Data 1 noiembrie 2021 10:36:32
Problema Cel mai lung subsir comun Scor 20
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");

stack <int> vect;
int i, j, n, m, M[1025], N[1025], sir[1025][1025], numar;

int main(){
    fin >> n >> m;

    for(i=0;i<n;i++)
        fin >> N[i];

    for(i=0;i<m;i++)
        fin >> M[i];

    for(i=1;i<n;i++)
        if(N[i] == M[1])
            while(i<=n)
                sir[i][1]=1, i++;

    for(i=1;i<m;i++)
        if(N[1] == M[i])
            while(i<=m)
                sir[1][i]=1, i++;

    for(i=2;i<=n;i++)
        for(j=2;j<=m;j++)
            if(N[i] == M[j])
                sir[i][j] = sir[i-1][j-1] + 1;
            else
                sir[i][j] = max(sir[i-1][j], sir[i][j-1]);

    fout << sir[n][m] << "\n";
    numar = sir[n][m];

    for(i=n;i>=1;i--)
        for(j=m;j>=1;j--)
            if(N[i] == M[j] && sir[i][j] == numar)
                vect.push(N[i]), i--, numar--;

    while(vect.empty() == 0)
        fout << vect.top() << " ", vect.pop();

    return 0;
}