Cod sursa(job #3342001)

Utilizator stfn99stefan stfn99 Data 22 februarie 2026 13:54:01
Problema Cel mai lung subsir comun Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int n,m,i,j,a[1030],b[1030],dp[1030][1030];
int main()
{
    set<int>s;
    fin >> n >> m;
    for(i = 1;i<=n;i++){
        fin >> a[i];
    }
    for(i = 1;i<=m;i++){
        fin >> b[i];
    }
    for(i = 1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(a[i] != b[j]){
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
            else
                dp[i][j] = dp[i-1][j-1]+1;
        }
    }
    i = n;
    j = m;
    fout << dp[i][j] << endl;;
    while(i!=0&&j!=0){
            if(a[i] == b[j]){
                s.insert(a[i]);
                i = i-1;
                j = j-1;
            }
            else{
                if(dp[i-1][j]<dp[i][j-1]){
                    j = j-1;
                }
                else{
                    i = i-1;
                }
            }
    }
    for(auto x:s){
        fout << x << ' ';
    }
    return 0;
}