Cod sursa(job #3292632)

Utilizator cosminccc7Cazacu Cosmin cosminccc7 Data 8 aprilie 2025 19:49:16
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("cmlsc.in");
ofstream out("cmlsc.out");
int dp[1050][1050],a[1050],na,b[1050],nb;
int main()
{in>>na>>nb;
stack <int>s;
for(int i=1;i<=na;i++)in>>a[i];
for(int i=1;i<=nb;i++)in>>b[i];

for(int i=1;i<=na;i++)
    for(int j=1;j<=nb;j++)
    if(a[i]==b[j])
    dp[i][j]=dp[i-1][j-1]+1;
else
    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);


    out<<dp[na][nb]<<endl;
    int i=na,j=nb;
    while(dp[i][j])
    if(a[i]==b[j])
    {s.push(a[i]);
    i--;
    j--;
    }
    else
    if(dp[i-1][j]<dp[i][j-1])j--;
    else
    i--;
    while(!s.empty())
    out<<s.top()<<" ",s.pop();
}