Pagini recente » Cod sursa (job #2307102) | Cod sursa (job #1896037) | Cod sursa (job #634345) | Cod sursa (job #3218729) | Cod sursa (job #2254982)
#include <bits/stdc++.h>
using namespace std;
class parser{
public:
parser() {}
parser(const char *file_name){
input_file.open(file_name,ios::in | ios::binary);
input_file.sync_with_stdio(false);
index&=0;
input_file.read(buffer,SIZE);}
inline parser &operator >>(int &n){
for (;buffer[index]<'0' or buffer[index]>'9';inc());
n&=0;
//sign&=0;
//sign|=(buffer[index-1]=='-');
for (;'0'<=buffer[index] and buffer[index]<='9';inc())
n=(n<<1)+(n<<3)+buffer[index]-'0';
//n^=((n^-n)&-sign);
return *this;}
~parser(){
input_file.close();}
private:
fstream input_file;
static const int SIZE=0x20000; ///0.2MB
char buffer[SIZE];
int index/*,sign*/;
inline void inc(){
if(++index==SIZE)
index=0,input_file.read(buffer,SIZE);}
};
class writer{
public:
writer() {};
writer(const char *file_name){
output_file.open(file_name,ios::out | ios::binary);
output_file.sync_with_stdio(false);
index&=0;}
inline writer &operator <<(int target){
aux&=0;
//sign&=0;
n=target;
/*if (n<0)
sign=1,
buffer[index]='-',
inc();
n^=((n^-n)&-sign);*/
if (!n)
nr[aux++]='0';
for (;n;n/=10)
nr[aux++]=n%10+'0';
for(;aux;inc())
buffer[index]=nr[--aux];
return *this;}
inline writer &operator <<(const char *target){
aux&=0;
while (target[aux])
buffer[index]=target[aux++],inc();
return *this;}
~writer(){
output_file.write(buffer,index);output_file.close();}
private:
fstream output_file;
static const int SIZE=0x10000; ///0.1MB
int index,aux,n/*,sign*/;
char buffer[SIZE],nr[24];
inline void inc(){
if(++index==SIZE)
index&=0,output_file.write(buffer,SIZE);}
};
parser f ("cmlsc.in");
writer t ("cmlsc.out");
int m,n;
vector <int> v1,v2,sol;
int max(const int x,const int y,const int z){
if (x>=y and x>=z) return x;
if (y>=x and y>=z) return y;
if (z>=x and z>=y) return z;
return -1;}
void read(){
f>>m>>n;
v1.resize(m);
v2.resize(n);
for (int i=0;i<m;++i)
f>>v1[i];
for (int i=0;i<n;++i)
f>>v2[i];
}
void solve(){
int d[m+1][n+1];
memset(d,0,sizeof(d));
for (int i=1;i<=m;++i)
for (int j=1;j<=n;++j)
d[i][j]=max(d[i-1][j-1]+(v1[i-1]==v2[j-1]),d[i-1][j],d[i][j-1]);
t<<d[m][n]<<"\n";
int i=m,j=n;
get_heritage:
if(d[i][j] == 0) goto fin;
if(v1[i-1]==v2[j-1])
{
sol.push_back(v1[i-1]);
--i,--j;
goto get_heritage;
}
else if(d[i][j] == d[i-1][j]){
--i;
goto get_heritage;}
else{
--j;
goto get_heritage;}
fin:for (int i=d[m][n]-1;i>=0;--i)
t<<sol[i]<<" ";
}
int main()
{
read();
solve();
return 0;
}