Pagini recente » Monitorul de evaluare | Cod sursa (job #3362238)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("cmlsc.in");
ofstream fout("cmlsc.out");
int main(){
int m, n;
fin >> m >> n;
vector<int> A(m), B(n);
for(int i = 0; i < m; i++){
fin >> A[i];
}
for(int i = 0; i < n; i++){
fin >> B[i];
}
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
vector<int> sol;
int i = m, j = n;
while(i > 0 && j > 0){
if(A[i-1] == B[j-1]){
sol.push_back(A[i-1]);
i--, j--;
}
else {
if(dp[i-1][j] > dp [i][j-1]) i--;
else j--;
}
}
reverse(sol.begin(), sol.end());
fout << dp[m][n] << endl;
for(auto c : sol){
fout << c << " ";
}
return 0;
}