Pagini recente » Cod sursa (job #3290960) | Cod sursa (job #144648) | Cod sursa (job #698268) | Cod sursa (job #2714804) | Cod sursa (job #3297259)
#include <stdio.h>
#include <vector>
#include <algorithm>
int main() {
FILE *fin = fopen( "cmlsc.in", "r" );
FILE *fout = fopen( "cmlsc.out", "w" );
int n, m;
fscanf( fin, "%d%d", &n, &m );
std::vector<int> a(n);
for( int i = 0; i < n; i++ )
fscanf( fin, "%d", &a[i] );
std::vector<int> b(m);
for( int i = 0; i < m; i++ )
fscanf( fin, "%d", &b[i] );
std::vector<std::vector<int>> mata(n+1, std::vector<int>(m+1, -1e9));
mata[0][0] = 0;
for( int i = 0; i < n; i++ ){
for( int j = 0; j < m; j++ ){
mata[i + 1][j + 1] = std::max( mata[i + 1][j + 1], mata[i + 1][j] );
mata[i + 1][j + 1] = std::max( mata[i + 1][j + 1], mata[i][j + 1] );
mata[i + 1][j + 1] = std::max( mata[i + 1][j + 1], (a[i] == b[j]) + mata[i][j] );
}
}
std::vector<int> ret; {
int i = n, j = m;
while( i || j ){
if( mata[i][j] == mata[i - 1][j] ){
i--;
}else if( mata[i][j] == mata[i][j - 1] ){
j--;
}else{
ret.push_back( a[--i] );
j--;
}
}
}
std::reverse( ret.begin(), ret.end() );
fprintf( fout, "%d\n", (int)ret.size() );
for( int x : ret ) fprintf( fout, "%d ", x );
fputc( '\n', fout );
fclose( fin );
fclose( fout );
return 0;
}