Cod sursa(job #2853924)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 20 februarie 2022 18:49:35
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;

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

int n, m, v1[1050], v2[1050], sir[1050], maxi;
int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        fin >> v1[i];
    }

    for (int i = 1; i <= m; ++i) {
        fin >> v2[i];
    }

    int j = 1;
    for (int i = 1; i <= m; ++i) {
        while(j <= n && ((v2[i] == v1[j] && sir[j - 1] < sir[j]) || v2[i] != v1[j])) {
            sir[j] = max(sir[j], sir[j - 1]);
            ++j;
        }

        if (j > n) {
            j = 1;
            continue;
        }

        sir[j] = max(sir[j], sir[j - 1]);
        ++sir[j];
    }

    for (int i = 1; i <= n; ++i) {
        if (sir[i] > maxi)
            maxi = sir[i];
    }

    fout << maxi << '\n';
    j = maxi;
    for (int i = 1; i <= n && j >= 1; ++i) {
        if (sir[i] == j) {
            v2[j] = v1[i];
            --j;
        }
    }

    for (int i = 1; i <= maxi; ++i)
        fout << v2[i] << ' ';
    return 0;
}