Advertisement
Guest User

Untitled

a guest
Nov 12th, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <utility>
  5. #include <climits>
  6.  
  7. std::pair<int, int> GetMax(const std::vector<int>& vector) {
  8.     int max = INT_MIN;
  9.     int max_ind = -1;
  10.     for (size_t i = 0; i < vector.size(); ++i) {
  11.         if (vector[i] > max) {
  12.             max = vector[i];
  13.             max_ind = i;
  14.         }
  15.     }
  16.     return std::make_pair(max, max_ind);
  17. }
  18.  
  19. struct Triple {
  20.     int first_;
  21.     int second_;
  22.     int third_;
  23.  
  24.     Triple(size_t first, size_t second, size_t third)
  25.     : first_(first), second_(second), third_(third) {
  26.     }
  27.  
  28.     Triple(int first, int second, int third)
  29.     : first_(first), second_(second), third_(third) {
  30.     }
  31. };
  32.  
  33. int Solution(const std::vector<int>& first, const std::vector<int>& second,
  34.         const std::vector<int>& third, std::vector<int>* sequence) {
  35.     std::vector<std::vector<std::vector<int>>> res;
  36.     std::vector<std::vector<std::vector<Triple>>> labels;
  37.     res = std::vector(first.size() + 1,
  38.             std::vector<std::vector<int>>(second.size() + 1,
  39.             std::vector<int>(third.size() + 1, 0)));
  40.     labels = std::vector(first.size() + 1,
  41.             std::vector<std::vector<Triple>>(second.size() + 1,
  42.             std::vector<Triple>(third.size() + 1,
  43.                     Triple(-1, -1, -1))));
  44.     for (size_t first_ind = 1; first_ind <= first.size(); ++first_ind) {
  45.         for (size_t second_ind = 1;
  46.         second_ind <= second.size(); ++second_ind) {
  47.             for (size_t third_ind = 1;
  48.             third_ind <= third.size(); ++third_ind) {
  49.                 std::pair<int, int> pair;
  50.                 if (first[first_ind - 1] == second[second_ind - 1] &&
  51.                 second[second_ind - 1] == third[third_ind - 1]) {
  52.                     pair = GetMax(std::vector<int> {res[first_ind - 1][second_ind][third_ind],
  53.                                        res[first_ind][second_ind - 1][third_ind],
  54.                                        res[first_ind][second_ind][third_ind - 1],
  55.                                        res[first_ind - 1][second_ind - 1][third_ind - 1] + 1});
  56.                     if (pair.second == 0) {
  57.                         labels[first_ind][second_ind][third_ind] =
  58.                                 labels[first_ind - 1][second_ind][third_ind];
  59.                     }
  60.                     if (pair.second == 1) {
  61.                         labels[first_ind][second_ind][third_ind] =
  62.                                 labels[first_ind][second_ind - 1][third_ind];
  63.                     }
  64.                     if (pair.second == 2) {
  65.                         labels[first_ind][second_ind][third_ind] =
  66.                                 labels[first_ind][second_ind][third_ind - 1];
  67.                     }
  68.                     if (pair.second == 3) {
  69.                         labels[first_ind][second_ind][third_ind] =
  70.                                 Triple{first_ind - 1, second_ind - 1,
  71.                                                                           third_ind - 1};
  72.                     }
  73.                 } else {
  74.                     pair = GetMax(std::vector<int>
  75.                             {res[first_ind - 1][second_ind][third_ind],
  76.                              res[first_ind][second_ind - 1][third_ind],
  77.                              res[first_ind][second_ind][third_ind - 1]});
  78.                     if (pair.second == 0) {
  79.                         labels[first_ind][second_ind][third_ind] =
  80.                                 labels[first_ind - 1][second_ind][third_ind];
  81.                     }
  82.                     if (pair.second == 1) {
  83.                         labels[first_ind][second_ind][third_ind] =
  84.                                 labels[first_ind][second_ind - 1][third_ind];
  85.                     }
  86.                     if (pair.second == 2) {
  87.                         labels[first_ind][second_ind][third_ind] =
  88.                                 labels[first_ind][second_ind][third_ind - 1];
  89.                     }
  90.                 }
  91.                 res[first_ind][second_ind][third_ind] = pair.first;
  92.             }
  93.         }
  94.     }
  95.     auto ind = labels[first.size()][second.size()][third.size()];
  96.     while (ind.first_ != -1 && ind.second_ != -1 && ind.third_ != - 1) {
  97.         (*sequence).push_back(first[ind.first_]);
  98.         ind = labels[ind.first_][ind.second_][ind.third_];
  99.     }
  100.     std::reverse(sequence->begin(), sequence->end());
  101.     return res[first.size()][second.size()][third.size()];
  102. }
  103.  
  104. int main() {
  105.     size_t first_size, second_size, third_size;
  106.     std::vector<int> first_vector, second_vector, third_vector;
  107.     std::cin >> first_size;
  108.     first_vector.reserve(first_size);
  109.     for (size_t it = 0; it < first_size; ++it) {
  110.         int variable;
  111.         std::cin >> variable;
  112.         first_vector.push_back(variable);
  113.     }
  114.     std::cin >> second_size;
  115.     second_vector.reserve(second_size);
  116.     for (size_t it = 0; it < second_size; ++it) {
  117.         int variable;
  118.         std::cin >> variable;
  119.         second_vector.push_back(variable);
  120.     }
  121.     std::cin >> third_size;
  122.     third_vector.reserve(third_size);
  123.     for (size_t it = 0; it < third_size; ++it) {
  124.         int variable;
  125.         std::cin >> variable;
  126.         third_vector.push_back(variable);
  127.     }
  128.     std::vector<int> res;
  129.     int max = Solution(first_vector, second_vector, third_vector, &res);
  130.     std::cout << max << std::endl;
  131.     for (const auto& elem : res) {
  132.         std::cout << elem << " ";
  133.     }
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement