fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int dp[2000][2000];
  4. vector<int> first,second;
  5. int lcs(int,int);
  6. int main()
  7. {
  8.     ios_base::sync_with_stdio(false);
  9.     cin.tie(NULL);
  10.     int tc,n,i,j,temp;
  11.     cin>>tc;
  12.     for(i=0;i<tc;i++){
  13.             temp=0;
  14.         while(cin>>n){
  15.             if(n==0){
  16.                 first.push_back(0);
  17.                 break;
  18.             }
  19.             first.push_back(n);
  20.         }
  21.         while(cin>>n){
  22.                 if(n==0 && second.empty())
  23.                     break;
  24.             if(n==0){
  25.                 second.push_back(0);
  26.                 memset(dp,-1,sizeof dp);
  27.                 temp=max(temp,lcs(0,0));
  28.                 second.clear();
  29.                 continue;
  30.             }
  31.             second.push_back(n);
  32.         }
  33.         cout<<temp<<endl;
  34.         first.clear();
  35.         second.clear();
  36.     }
  37.     return 0;
  38. }
  39. int lcs(int i,int j)
  40. {
  41.     if(first[i]==0 || second[j]==0)
  42.         return 0;
  43.     if(dp[i][j]!=-1)
  44.         return dp[i][j];
  45.     if(first[i]==second[j])
  46.         return 1+lcs(i+1,j+1);
  47.     return max(lcs(i,j+1),lcs(i+1,j));
  48. }
  49.  
Success #stdin #stdout 0.01s 19316KB
comments (?)
stdin
copy 
3
1 2 3 4 5 6 7 8 9 0
1 3 8 2 0
2 5 7 8 9 0
1 1 1 1 1 1 2 3 0
1 3 1 3 5 7 8 9 3 4 0
1 2 35 0
0
1 3 5 7 0
3 7 5 1 0
0
1 2 1 1 0
1 1 1 0
0
stdout
copy 
6
2
3
https://ideone.com/0zy0gj
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!