Advertisement
AkirusG

Untitled

Nov 16th, 2014
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <limits>
  7. #include <map>
  8. #include <cstdlib>
  9. #include <cmath>
  10. #include <set>
  11. #include <bitset>
  12. #include <string>
  13. #include <iomanip>
  14. #include <deque>
  15.  
  16. using namespace std;
  17.  
  18. int main(){
  19.     //freopen("", "r", stdin); freopen("", "w", stdout);
  20.     //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  21.     ios::sync_with_stdio(false);
  22.  
  23.     int n, m;
  24.    
  25.     cin >> n;
  26.     vector<int> a(n);
  27.     for(int i = 0; i < n; i++)
  28.         cin >> a[i];
  29.    
  30.     cin >> m;
  31.     vector<int> b(m);
  32.     for(int i = 0; i < m; i++)
  33.         cin >> b[i];
  34.    
  35.     vector<vector<int> > mat(n, vector<int>(m, 0));
  36.    
  37.     for(int i = 0; i < n; i++){
  38.         for(int j = 0; j < m; j++){
  39.             mat[i][j] = max( i > 0 ? mat[i - 1][j] : 0, j > 0 ? mat[i][j - 1] : 0);
  40.             if(a[i] == b[j]){
  41.                 mat[i][j] = max(mat[i][j], (i > 0 && j > 0 ? mat[i - 1][j - 1] : 0) + 1);
  42.                 // cout << i <<  " " << j;
  43.             }
  44.         }
  45.     }
  46.    
  47. //    for(int i = 0; i < n; i++){
  48. //        for(int j = 0; j < m; j++){
  49. //            cout << mat[i][j] << " ";
  50. //        }
  51. //        cout << endl;
  52. //    }
  53.    
  54.     int mx = 0;
  55.     int mi = 0;
  56.    
  57.     for(int i = 0; i < n; i++){
  58.         for(int j = 0; j < m; j++){
  59.             if(mat[i][j] > mx){
  60.                 mx = mat[i][j];
  61.                 mi = i;
  62.             }
  63.         }
  64.     }
  65.    
  66.     for(int i = mi - mx + 1; i <= mi; i++)
  67.         cout << a[i] << " ";
  68.    
  69.     return  0;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement