Cod sursa(job #3152379)

Utilizator LauraNaduLaura Nadu LauraNadu Data 24 septembrie 2023 21:15:37
Problema Cel mai lung subsir comun Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include<fstream>
#include<iostream>

using namespace std;

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

    int sizeA, sizeB;
    read >> sizeA >> sizeB;
    int *a = (int*)malloc((sizeA + 1) * sizeof(int));
    int *b = (int*)malloc((sizeB + 1) * sizeof(int));
    int *c = (int*)calloc((sizeA + 1) * (sizeB + 1), sizeof(int));

    for (int i = 1; i <= sizeA; i++) {
        read >> a[i];
    }

    for (int i = 1; i <= sizeB; i++) {
        read >> b[i];
    }

    for (int i = 1; i <= sizeA; i++) {
        for (int j = 1; j <= sizeB; j++) {
            if (a[i] == b[j]) {
                c[i * (sizeB + 1) + j] = c[(i - 1) * (sizeB + 1) + j - 1] + 1;
            } else {
                c[i * (sizeB + 1) + j] = max(c[(i - 1) * (sizeB + 1) + j], c[i * (sizeB + 1) + j - 1]);
            }
        }
    }

    write << c[(sizeA + 1) * (sizeB + 1) - 1] << "\n";

    int *solution = (int*)malloc(c[(sizeA + 1) * (sizeB + 1) - 1] * sizeof(int));
    int len = 0;
    for (int i = sizeA, j = sizeB; i > 0;) {
        if (a[i] == b[j]) {
            solution[len++] = a[i];
            i--;
            j--;
        } else if (c[(i - 1) * (sizeB + 1) + j] >= c[i * (sizeB + 1) + j - 1])
            i--;
        else j--;
    }

    for (int i = len - 1; i >= 0; i--) {
        write << solution[i] << " ";
    }
}