Cod sursa(job #1989726)

Utilizator S_AndyAndrei S S_Andy Data 8 iunie 2017 17:14:22
Problema Cel mai lung subsir comun Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>

using namespace std;

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

int main()
{
    short n, m, *a, b, *ab, c[1024], max_ab, i, j;
    fin >> n >> m;
    a = new short[n+1];
    ab = new short[(n+1) * (m+1)];
    ab[0] = 0;
    for(i = 1; i <= n; ++i) {
        fin >> a[i];
        ab[i*(m+1)] = 0;
    }
    for(j = 1; j <= m; ++j) {
        ab[j] = 0;
        fin >> b;
        for(i = 1; i <= n; ++i) {
            (b == a[i])?(ab[i*(m+1) + j] = ab[(i-1)*(m+1) + j-1] + 1):(ab[i*(m+1) + j] = max(ab[(i-1)*(m+1) + j],ab[i*(m+1) + j-1]));
        }
    }

    max_ab = ab[(m+1)*(n+1) - 1];
    fout << max_ab << "\n";

    i = n;
    j = m;
    while(max_ab) {
        if(ab[i*(m+1) + j] > ab[(i-1)*(m+1) + j] && ab[i*(m+1) + j] > ab[i*(m+1) + j - 1] && ab[i*(m+1) + j] > ab[(i-1)*(m+1) + j - 1]) {
            c[--max_ab] = a[i];
            --i;
            --j;
        }
        else if(ab[i*(m+1) + j - 1] > ab[(i-1)*(m+1) + j]) {
            --j;
        }
        else {
            --i;
        }
    }
    for(i = 0; i < ab[(m+1)*(n+1) - 1]; ++i) {
        fout << c[i] << " ";
    }

}