Cod sursa(job #3322963)

Utilizator alexx.bxlFlorea Alexandru-Mihai alexx.bxl Data 16 noiembrie 2025 13:02:48
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int D[1025][1025], m, n, i, j, sir[1025], nr = 0;
int main()
{
    fin >> m >> n;
    int A[m + 1], B[n + 1];
    for(i = 1; i <= m; i++)
        fin >> A[i];
    for(i = 1; i <= n; i++)
        fin >> B[i];
    for(i = 1; i <= m; i++)
        for(j = 1; j <= n; j++)
            if(A[i] == B[j])
                D[i][j] = 1 + D[i - 1][j - 1];
            else D[i][j] = max(D[i - 1][j], D[i][j - 1]);
    while(i > 0 && j > 0)
        if(A[i] == B[j])
        {
            sir[++nr] = A[i];
            --i;
            --j;
        }
        else if(D[i - 1][j] < D[i][j - 1])
            --j;
        else --i;
    fout << nr << endl;
    for(i = nr; i >= 1; --i)
        fout << sir[i] << " ";
}