Cod sursa(job #2468995)

Utilizator ValentinStStamate Valentin ValentinSt Data 6 octombrie 2019 13:18:10
Problema Cel mai lung subsir comun Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
using namespace std;

#define max(a, b) ( a > b ? a : b )
#define MAX 1024

int a[MAX], b[MAX], arr[MAX][MAX], sir[MAX];

int main() {
    ifstream in("cmlsc.in");
    ofstream out("cmlsc.out");

    int m, n;
    in>>m>>n;

    for(int i = 1; i <= m; i++)
        in>>a[i];

    for(int i = 1; i <= n; i++)
        in>>b[i];

    for(int i = 0; i <= n; i++)
        arr[i][0] = 0;
    for(int i = 0; i <= m; i++)
        arr[0][i] = 0;

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

    out<<arr[n][m]<<"\n";

    int index = -1;

    while(n >= 1 || m >= 1){
        int i = n, j = m;
        if(a[j] == b[i]){
            sir[++index] = a[j];
            m--,n--;
        } else {
            if(arr[i][j - 1] > arr[i - 1][j]){
                m--;
            } else {
                n--;
            }
        }
    }

    for(int i = index; i >= 0; i--){
        out<<sir[i]<<" ";
    }


    return 0;
}