Cod sursa(job #2613625)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 10 mai 2020 01:01:39
Problema Cel mai lung subsir comun Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");

#define pb push_back
#define x first
#define y second
#define Nmax 1028

vector<int> v;

int n, m, mx = 0, ii, jj;
int a[Nmax], b[Nmax];

int dp[Nmax][Nmax];

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; ++i)
        fin >> a[i];
    for (int j = 1; j <= m; ++j)
        fin >> b[j];

    dp[1][0] = 0;
    dp[0][1] = 0;
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);

            if (a[i] == b[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;

            if (dp[i][j] > mx)
            {
                mx = dp[i][j];
                ii = i;
                jj = j;
            }
        }

    fout << dp[n][m] << '\n';

    int i = ii, j = jj;

    while (i > 0 && j > 0)
    {
        if (a[i] == b[j])
        {
            v.pb(a[i]);
            --i;
            --j;
        }

        if (dp[i - 1][j] > dp[i][j - 1])
            i--;
        else
            j--;
    }

    reverse(v.begin(), v.end());

    for (auto nr : v)
        fout << nr << ' ';
    return 0;
}