Cod sursa(job #3360585)

Utilizator iulia_toderica16Iulia Toderica iulia_toderica16 Data 14 iulie 2026 19:44:09
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <iostream>
using namespace std;

struct nume {
    int nr;
    unsigned st   : 1;
    unsigned sus   : 1;
    unsigned diag : 1;
}mat[1028][1028];//prima linie ii primul sir de nr
//prima coloana ii al doilea sir de nr
//a doua linie si coloana este plina de zerouri ca sa fie algoritmul fara ifuri la margini (padding)

int main(){
    int n,m;
    ifstream fin("cmlsc.in");
    ofstream fout("cmlsc.out");
    fin>>m>>n;
    for (int i=2; i<m+2; ++i)
        fin>>mat[0][i].nr;
    for (int i=2; i<n+2; ++i)
        fin>>mat[i][0].nr;

    for (int i=2; i<n+2; ++i){
        for (int j=2; j<m+2; ++j){

            if (mat[i][0].nr==mat[0][j].nr){
                mat[i][j].nr=1+mat[i-1][j-1].nr;
                mat[i][j].diag=true;
            }
            else if (mat[i][j-1].nr > mat[i-1][j].nr){
                mat[i][j].nr=mat[i][j-1].nr;
                mat[i][j].st=true;
            }
            else if (mat[i][j-1].nr < mat[i-1][j].nr){
                mat[i][j].nr=mat[i-1][j].nr;
                mat[i][j].sus=true;
            }
            else {
                mat[i][j].nr=mat[i-1][j].nr;
                mat[i][j].sus=true;
                mat[i][j].st=true;
            }
        }
    }
    int maxx=mat[n+1][m+1].nr;//subsecventa maxima
    fout<<maxx<<'\n';
    int sir[1025], nsir=0;
    int i=n+1, j=m+1;
    while(i>=2 && j>=2){
            if (mat[i][j].diag==true){
                sir[nsir]=mat[i][0].nr;
                ++nsir;
                i--; j--; //diagonala
            }
            else if (mat[i][j].st==true){
                j--;

            }else i--;
    }
    for (int k=nsir-1; k>=0; --k)
        fout<<sir[k]<<' ';
}