Cod sursa(job #2260628)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 15 octombrie 2018 11:41:17
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb

#include <bits/stdc++.h>
using namespace std;


int a[1100], b[1100];
int dp[1100][1100];
int n, m;
int r[1100];

int main()
{
    ifstream in("cmlsc.in");
    ofstream out("cmlsc.out");
    in >> n >> m;
    for (int i(1); i <= n; i++)
        in >> a[i];
    for (int i(1); i <= m; i++)
        in >> b[i];

    a[0] = b[0] = -1;

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

    int ans = dp[n][m];
    int cnt(ans);
    out << ans << '\n';
    for (int i(n), j(m); i && j; ) {
        if (dp[i][j] == dp[i - 1][j]) {
            i--;
            continue;
        }
        if (dp[i][j] == dp[i][j - 1]) {
            j--;
            continue;
        }

        r[cnt--] = a[i];
        i--, j--;
    }

    for (int i(1); i <= ans; i++)
        out << r[i] << ' ';

    return 0;
}