PZDC

#include <iostream>
#include <string>
#include <vector>
#include <tuple>

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    std::string input;
    std::cin >> input;

    if (input.length() < 2)
        return 0;

    const int size = input.length();

    std::vector<std::vector<std::tuple<std::string, bool, int, int>>> memo (
        size,                                                                 // размер
    std::vector<std::tuple<std::string, bool, int, int>> (                // храним строку, корректность, правую и левую границы
            size,
        std::make_tuple("", false, 1000, -1)
        )
    );

    for (int i = 0, q = 0; i < size; i++, q++)
    {
        std::get<0>(memo[i][q]).push_back(input[i]);
        std::get<2>(memo[i][q]) = i;
        std::get<3>(memo[i][q]) = q;
    }

    for (int r = 1; r < size; r++) // диагонали
    {
        for (int i = 0, q = r; q < size; i++, q++) // обход по-диагонали
        {
            std::string best;
            bool correct = false;
            int right = 1000, left = -1;

            for (int s = 1; s <= r; s++) // обход по-верху
            {
                for (int d = 0; d < s; d++) // обход по-низу
                {
                    if (std::get<1>(memo[i][q - s])) // 1 корректна
                    {
                        if (std::get<1>(memo[i + r - d][q])) // 2 корректна
                        {
                            if (std::get<0>(memo[i + r - d][q]).length() + std::get<0>(memo[i][q - s]).length() >= best.length())
                            {
                                best = std::get<0>(memo[i][q - s]) + std::get<0>(memo[i + r - d][q]);
                                right = i; left = q;
                                correct = true;
                            }
                        }

                        else if (std::get<0>(memo[i][q - s]).length() >= best.length()) // 2 не корректна
                        {
                            best = std::get<0>(memo[i][q - s]);
                            right = std::get<2>(memo[i][q - s]);
                            left = std::get<3>(memo[i][q - s]);
                            correct = true;
                        }
                    }

                    else if (std::get<1>(memo[i + r - d][q])) // 1 не корректна, 2 корректна
                    {
                        if (std::get<0>(memo[i + r - d][q]).length() >= best.length())
                        {
                            best = std::get<0>(memo[i + r - d][q]);
                            right = std::get<2>(memo[i + r - d][q]);
                            left = std::get<3>(memo[i + r - d][q]);
                            correct = true;
                        }
                    }

                    else // обе не корректны
                    {
                        std::cout << "PIZDA " << i << " " << q - s << " " << i + r - d << " " << q << '\n';

                        auto check = [&memo, &i, &q, &s, &r, &d, &best, &correct, &left, &right](const char ch1, const char ch2) // чекаем скобки
                        {
                            if (std::get<0>(memo[i][q - s]).back() == ch1 && std::get<0>(memo[i + r - d][q]).back() == ch2)
                            {
                                std::cout << "OK1 " << i << " " << q - s << " " << i + r - d << " " << q << '\n';

                                if (std::get<2>(memo[i][q - s]) < right && std::get<3>(memo[i + r - d][q]) > left)
                                {
                                    best = std::get<0>(memo[i][q - s]) + best + std::get<0>(memo[i + r - d][q]);
                                    right = std::get<2>(memo[i][q - s]);
                                    left = std::get<3>(memo[i + r - d][q]);
                                    correct = true;

                                    std::cout << "OK2 " << i << " " << q - s << " " << i + r - d << " " << q << '\n';
                                }
                            }
                        };

                        if (!std::get<0>(memo[i][q - s]).empty() && !std::get<0>(memo[i + r - d][q]).empty())
                        {
                            if (std::get<0>(memo[i][q - s]).front() == '(') check('(', ')');
                            else if (std::get<0>(memo[i][q - s]).front() == '{') check('{', '}');
                            else check('[', ']');
                        }
                    }
                }
            }

            std::get<0>(memo[i][q]) = std::move(best);
            std::get<1>(memo[i][q]) = correct;
            std::get<2>(memo[i][q]) = right;
            std::get<3>(memo[i][q]) = left;
        }
    }

    std::cout << std::get<0>(memo[0][size - 1]);

    return 0;
}