Bracket sequence

// clang-format off
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#ifdef DO_DBG
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#define dout cerr
#define debug true
#else
#define dbg(...)
#define dout if (0) cerr
#define debug false
#endif
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
template <typename T> using v = vector<T>; template <typename T> using us = unordered_set<T>; template <typename K, typename V> using p = pair<K,V>;
template <typename K, typename V> using um = unordered_map<K, V>; template <typename K, typename V> using p = pair<K, V>;
template <typename T> using pq = priority_queue<T>; template <typename T> using nl = numeric_limits<T>; template <typename T> using il = initializer_list<T>;
constexpr int MOD = 1e9 + 7; constexpr int INF = 1e9; constexpr ld EPS = 1e-9;
#define fr(i,a,b) for (size_t i = a; i < b; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin.exceptions(cin.failbit);
#define frr(i,a,b) for (size_t i = b-1; i >= a; i--)
#define frs(i,a,b) for (ll i = a; i < b; i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sq(x) ((x) * (x))
template <typename... Args> void read(Args&... args) { ((cin >> args), ...); }
#define d(...) int __VA_ARGS__; read(__VA_ARGS__);
#define dll(...) ll __VA_ARGS__; read(__VA_ARGS__);
#define dv(x, n) vector<int> x(n); for (int i = 0; i < n; i++) cin >> x[i];
#define dvll(x, n) vector<long long> x(n); for (int i = 0; i < n; i++) cin >> x[i];
#define dvd(x, n) vector<double> x(n); for (int i = 0; i < n; i++) cin >> x[i];
ll ipow(ll a,int b){ll r=1;for(;b;b>>=1,a*=a)if(b&1)r*=a;return r;}
template<class F>struct y_combinator{F f;template<class...Args>decltype(auto)operator()(Args&&...args)const{return f(*this,forward<Args>(args)...);}};
constexpr auto get_nums=[]<typename T>(T&&s){istringstream iss(forward<T>(s));return vector<int>{istream_iterator<int>{iss},{}};};
#define even(x) ((x)%2==0)
#define odd(x) ((x)%2!=0)
#define sz(s) ((ll)s.size())
#define dist(v,iter) distance(v.begin(),iter)
// clang-format on

int main() {
  fastio;
  string s;
  getline(cin, s);
  auto n = sz(s);
  if (n <= 1) {
    cout << "-1\n";
    return 0;
  }
  // dp[i] is the longest regular bracket sequence that ends at i
  v<ll> dp(n);
  frs(i, 1, n) {
    // we need a closing paren at the end
    if (s[i] == ')') {
      // if the previous paren was opening, we just add 2
      if (s[i - 1] == '(') {
        dp[i] = (i - 2) >= 0 ? (dp[i - 2] + 2) : 2;
      } else {
        // the previous paren was closing
        // then we can check if we are enclosing another regular bracket
        // sequence
        auto enclosedStart = i - dp[i - 1] - 1;
        if (enclosedStart >= 0 && s[enclosedStart] == '(') {
          dp[i] =
              dp[i - 1] + 2 + ((enclosedStart > 0) ? dp[enclosedStart - 1] : 0);
        }
      }
    }
  }
  auto me = max_element(all(dp));
  if (*me) {
    frs(i, dist(dp, me) - *me, dist(dp, me)) { cout << s[i + 1]; }
    cout << '\n';
  } else {
    cout << "-1\n";
  }

  // also learned to prefer signed numbers, and dist() instead of vec.end() -
  // iter to get the index like an idiot

  // my first try, clearly does not work:
  // an regular bracket sequence has an equal amount of ( and )
  // going from left to right, there is always at least as much ( as )
  // so ()) is not valid.
  // ll lbr = 0;
  // ll rbr = 0;
  // size_t l = 0;
  // ll maxl = 0, maxr = 0;
  // fr(r, 0, s.size()) {
  //   dbg(l, r, lbr, rbr);
  //   if (s[r] == '(') {
  //     lbr++;
  //   } else if (s[r] == ')') {
  //     rbr++;
  //   }
  //   if (rbr > lbr) {
  //     while (rbr > lbr) {
  //       if (s[l] == '(') {
  //         lbr--;
  //       } else if (s[l] == ')') {
  //         rbr--;
  //       }
  //       l++;
  //       dbg(l);
  //     }
  //     if (l > r) {
  //       r = l - 1;
  //     }
  //   } else {
  //     if (r - l > maxr - maxl && lbr == rbr) {
  //       maxl = l;
  //       maxr = r;
  //     }
  //   }
  // }
  // if (maxl == 0 && maxr == 0) {
  //   cout << "-1\n";
  // } else {
  //   dbg(maxl, maxr);
  //   fr(i, maxl, maxr + 1) { cout << s[i]; }
  //   cout << '\n';
  // }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED

Test 65

Verdict: ACCEPTED