Pagini recente » Cod sursa (job #2209040) | Cod sursa (job #3350008) | Cod sursa (job #2058290) | Cod sursa (job #3338916) | Cod sursa (job #3338918)
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
std::ifstream f("cmlsc.in");
std::ofstream g("cmlsc.out");
int n, m, dp[1025][1025];
int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
// f.tie(NULL);
// g.tie(NULL);
f >> n >> m;
std::vector<int> a(n + 5), b(m + 5);
for(int i = 1; i <= n; ++i)
f >> a[i];
for(int j = 1; j <= m; ++j)
f >> b[j];
for(int i = 1; i <= m; ++i)
for(int j = 1; j <= n; ++j)
dp[i][j] = std::max({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1] + (b[i] == a[j])});
int indi = m, indj = n;
std::vector<int> sol;
while(0 < indi and 0 < indj and dp[indi][indj]){
while(dp[indi][indj] == dp[indi - 1][indj] and 0 < indi)
indi --;
while(dp[indi][indj] == dp[indi][indj - 1] and 0 < indj)
indj --;
sol.push_back(b[indi]);
--indi, --indj;
//std::cout << indi << ' ' << indj << '\n';
}
g << sol.size() << '\n';
for(int i = sol.size() - 1; i >= 0; --i)
g << sol[i] << ' ';
return 0;
}