Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <utility>
- #include <climits>
- std::pair<int, int> GetMax(const std::vector<int>& vector) {
- int max = INT_MIN;
- int max_ind = -1;
- for (size_t i = 0; i < vector.size(); ++i) {
- if (vector[i] > max) {
- max = vector[i];
- max_ind = i;
- }
- }
- return std::make_pair(max, max_ind);
- }
- struct Triple {
- int first_;
- int second_;
- int third_;
- Triple(size_t first, size_t second, size_t third)
- : first_(first), second_(second), third_(third) {
- }
- Triple(int first, int second, int third)
- : first_(first), second_(second), third_(third) {
- }
- };
- int Solution(const std::vector<int>& first, const std::vector<int>& second,
- const std::vector<int>& third, std::vector<int>* sequence) {
- std::vector<std::vector<std::vector<int>>> res;
- std::vector<std::vector<std::vector<Triple>>> labels;
- res = std::vector(first.size() + 1,
- std::vector<std::vector<int>>(second.size() + 1,
- std::vector<int>(third.size() + 1, 0)));
- labels = std::vector(first.size() + 1,
- std::vector<std::vector<Triple>>(second.size() + 1,
- std::vector<Triple>(third.size() + 1,
- Triple(-1, -1, -1))));
- for (size_t first_ind = 1; first_ind <= first.size(); ++first_ind) {
- for (size_t second_ind = 1;
- second_ind <= second.size(); ++second_ind) {
- for (size_t third_ind = 1;
- third_ind <= third.size(); ++third_ind) {
- std::pair<int, int> pair;
- if (first[first_ind - 1] == second[second_ind - 1] &&
- second[second_ind - 1] == third[third_ind - 1]) {
- pair = GetMax(std::vector<int> {res[first_ind - 1][second_ind][third_ind],
- res[first_ind][second_ind - 1][third_ind],
- res[first_ind][second_ind][third_ind - 1],
- res[first_ind - 1][second_ind - 1][third_ind - 1] + 1});
- if (pair.second == 0) {
- labels[first_ind][second_ind][third_ind] =
- labels[first_ind - 1][second_ind][third_ind];
- }
- if (pair.second == 1) {
- labels[first_ind][second_ind][third_ind] =
- labels[first_ind][second_ind - 1][third_ind];
- }
- if (pair.second == 2) {
- labels[first_ind][second_ind][third_ind] =
- labels[first_ind][second_ind][third_ind - 1];
- }
- if (pair.second == 3) {
- labels[first_ind][second_ind][third_ind] =
- Triple{first_ind - 1, second_ind - 1,
- third_ind - 1};
- }
- } else {
- pair = GetMax(std::vector<int>
- {res[first_ind - 1][second_ind][third_ind],
- res[first_ind][second_ind - 1][third_ind],
- res[first_ind][second_ind][third_ind - 1]});
- if (pair.second == 0) {
- labels[first_ind][second_ind][third_ind] =
- labels[first_ind - 1][second_ind][third_ind];
- }
- if (pair.second == 1) {
- labels[first_ind][second_ind][third_ind] =
- labels[first_ind][second_ind - 1][third_ind];
- }
- if (pair.second == 2) {
- labels[first_ind][second_ind][third_ind] =
- labels[first_ind][second_ind][third_ind - 1];
- }
- }
- res[first_ind][second_ind][third_ind] = pair.first;
- }
- }
- }
- auto ind = labels[first.size()][second.size()][third.size()];
- while (ind.first_ != -1 && ind.second_ != -1 && ind.third_ != - 1) {
- (*sequence).push_back(first[ind.first_]);
- ind = labels[ind.first_][ind.second_][ind.third_];
- }
- std::reverse(sequence->begin(), sequence->end());
- return res[first.size()][second.size()][third.size()];
- }
- int main() {
- size_t first_size, second_size, third_size;
- std::vector<int> first_vector, second_vector, third_vector;
- std::cin >> first_size;
- first_vector.reserve(first_size);
- for (size_t it = 0; it < first_size; ++it) {
- int variable;
- std::cin >> variable;
- first_vector.push_back(variable);
- }
- std::cin >> second_size;
- second_vector.reserve(second_size);
- for (size_t it = 0; it < second_size; ++it) {
- int variable;
- std::cin >> variable;
- second_vector.push_back(variable);
- }
- std::cin >> third_size;
- third_vector.reserve(third_size);
- for (size_t it = 0; it < third_size; ++it) {
- int variable;
- std::cin >> variable;
- third_vector.push_back(variable);
- }
- std::vector<int> res;
- int max = Solution(first_vector, second_vector, third_vector, &res);
- std::cout << max << std::endl;
- for (const auto& elem : res) {
- std::cout << elem << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement