Pagini recente » Cod sursa (job #1430234) | Cod sursa (job #2107299) | Cod sursa (job #1431548) | Cod sursa (job #1028479) | Cod sursa (job #2638137)
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
int t, n, m, k, a[2000], b[1030];
int dp[1025][1025], dir[1025][1025];
ifstream fin("cmlsc.in"); ofstream fout("cmlsc.out");
#define cin fin
#define cout fout
int32_t main(){
INIT
cin>>n>>m;
for(int i=1; i<=n; i++){cin>>a[i];}
for(int i=1; i<=m; i++){cin>>b[i];}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(a[i]==b[j]){
dp[i][j]=dp[i-1][j-1]+1; dir[i][j]=2; continue;
}
if( dp[i-1][j-1]>=max(max(dp[i-1][j], dp[i][j-1]), dp[i][j]) ){
dir[i][j]=2; dp[i][j]=dp[i-1][j-1];
}
if( dp[i-1][j]>=max(max(dp[i-1][j-1], dp[i][j-1]), dp[i][j]) ){
dir[i][j]=1; dp[i][j]=dp[i-1][j];
}
if( dp[i][j-1]>=max(max(dp[i-1][j], dp[i-1][j-1]), dp[i][j]) ){
dir[i][j]=3; dp[i][j]=dp[i][j-1];
}
}
}
int x=m, y=n;
cout<<dp[y][x]<<"\n";
vector<int> res;
while(x>0 && y>0){
int d=dir[y][x];
if(d==1){
if(dp[y-1][x]<dp[y][x] ){
res.pb(a[y]);
}
y--;
}
if(d==2){
if(dp[y-1][x-1]<dp[y][x]){
res.pb(a[y]);
}
x--; y--;
}
if(d==3){
if(dp[y][x-1]<dp[y][x]){
res.pb(a[y]);
}
x--;
}
}
for(int i=res.size()-1; i>=0; i--){
cout<<res[i]<<" ";
}
return 0;
}