SHARE
TWEET

Untitled

zangezi_is_dead Sep 20th, 2019 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <list>
  5. #include <stack>
  6. #include <optional>
  7. #include <utility>
  8. #include <algorithm>
  9.  
  10. using std::stack;
  11. using std::vector;
  12. using std::optional;
  13. using std::list;
  14. using std::cin;
  15. using std::cout;
  16. using std::pair;
  17. using std::max;
  18. using std::min;
  19.  
  20. vector<int> InputSequence(size_t length);
  21.  
  22. void PrintSequence(const vector<int>& sequence);
  23.  
  24. int main() {
  25.  
  26.     size_t first_length, second_length, third_length;
  27.  
  28.     cin >> first_length;
  29.     vector<int> FirstSequence = InputSequence(first_length);
  30.     FirstSequence.insert(FirstSequence.begin(), 0);
  31.     cin >> second_length;
  32.     vector<int> SecondSequence = InputSequence(second_length);
  33.     SecondSequence.insert(SecondSequence.begin(), 0);
  34.     cin >> third_length;
  35.     vector<int> ThirdSequence = InputSequence(third_length);
  36.     ThirdSequence.insert(ThirdSequence.begin(), 0);
  37.  
  38.     ++first_length;
  39.     ++second_length;
  40.     ++third_length;
  41.  
  42.     vector<vector<vector<int>>> matrix (first_length);
  43.     for (size_t row = 0; row < first_length; ++row) {
  44.         matrix[row].resize(second_length);
  45.         for (size_t column = 0; column < second_length; ++column) {
  46.                 matrix[row][column].resize(third_length);
  47.         }
  48.     }
  49.  
  50.     vector<int> results;
  51.     int maximum = 0;
  52.     size_t xopt = 0;
  53.     size_t yopt = 0;
  54.     size_t zopt = 0;
  55.  
  56.     for (size_t row = 0; row < first_length; ++row) {
  57.         for (size_t column = 0; column < second_length; ++column) {
  58.             for (size_t height = 0; height < third_length; ++height) {
  59.  
  60.                 if (row * column * height == 0) {
  61.  
  62.                     matrix[row][column][height] = 0;
  63.  
  64.                 } else if ((FirstSequence[row] == SecondSequence[column]) &&
  65.                             (FirstSequence[row] == ThirdSequence[height])) {
  66.  
  67.                     matrix[row][column][height] = matrix[row - 1][column - 1][height - 1] + 1;
  68.  
  69.                     if (matrix[row][column][height] > maximum) {
  70.  
  71.                         maximum = matrix[row][column][height];
  72.                         xopt = row;
  73.                         yopt = column;
  74.                         zopt = height;
  75.                     }
  76.  
  77.                 } else {
  78.  
  79.                     matrix[row][column][height] = max(matrix[row - 1][column][height],
  80.                             max(matrix[row][column - 1][height], matrix[row][column][height - 1]));
  81.                 }
  82.             }
  83.         }
  84.     }
  85.  
  86.     size_t diag = maximum;
  87.     vector<int> result (maximum);
  88.  
  89.     while (diag > 0) {
  90.  
  91.         while (matrix[xopt][yopt][zopt] == matrix[xopt - 1][yopt][zopt]) {
  92.             --xopt;
  93.         }
  94.  
  95.         while (matrix[xopt][yopt][zopt] == matrix[xopt][yopt - 1][zopt]) {
  96.             --yopt;
  97.         }
  98.  
  99.         while (matrix[xopt][yopt][zopt] == matrix[xopt][yopt][zopt - 1]) {
  100.             --zopt;
  101.         }
  102.  
  103.         if (matrix[xopt][yopt][zopt] > matrix[xopt - 1][yopt - 1][zopt - 1]) {
  104.             result[diag - 1] = FirstSequence[xopt];
  105.             --diag;
  106.         }
  107.         --xopt;
  108.         --yopt;
  109.         --zopt;
  110.     }
  111.  
  112.     cout << maximum << '\n';
  113.     PrintSequence(result);
  114.     return 0;
  115. }
  116.  
  117. vector<int> InputSequence(size_t length) {
  118.     vector<int> sequence(length);
  119.     for (size_t count = 0; count < length; ++count) {
  120.         cin >> sequence[count];
  121.     }
  122.     return sequence;
  123. }
  124.  
  125. void PrintSequence(const vector<int>& sequence) {
  126.     for (auto i : sequence) {
  127.         cout << i << ' ';
  128.     }
  129.     cout << '\n';
  130. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top