Trước tiên, với mỗi dấu ~')'~, ta cần tìm dấu ~'('~ tương ứng với nó bằng cách sử dụng stack trong độ phức tạp là ~O(N)~ như sau: Xét lần lượt các kí tự từ trái sang phải, nếu gặp kí tự ~'('~ thì ta thêm vào stack, nếu gặp kí tự ~')'~ thì phần tử cuối cùng của stack chính là ~'('~ khớp với nó (nếu stack rỗng thì không có ~'('~ khớp với nó), ta gọi mảng này là mảng ~pos~ (~pos_i~ là ~'('~ tương ứng với ~i~).

Với câu hỏi thứ nhất, ta cần viết hàm ~count(S, K)~ là số dãy con của ~S~ là dãy ngoặc đúng có bậc không lớn hơn ~K~, thì đáp án sẽ là ~count(S, K) - count(S, K - 1)~. Ta sẽ tính ~count(S, K)~ bằng quy hoạch động. Gọi ~dp_i~ là số dãy ngoặc đúng bậc không lớn hơn ~K~ kết thúc tại ~i~, thì nếu dãy con ~S_{pos_i...i}~ có bậc không lớn hơn ~K~ thì ~dp_i = dp_{pos_i - 1} + 1~. Đáp án sẽ bằng ~\sum_{i = 1} ^ {|S|} dp_i~.

Với câu hỏi thứ hai, vì là tìm max nên ta không thể làm như câu hỏi thứ nhất được. Ta sẽ xét các dãy con là dãy ngoặc đúng bậc ~K~ và tìm phần lớn nhất sang hai bên mà bậc vẫn không lớn hơn ~K~. Ta gọi ~left_i~ là độ dài dãy ngoặc đúng bậc không lớn hơn ~K~ dài nhất kết thúc tại ~i~. Ta giải quyết tương tự bài toán trên, nếu dãy con ~S_{pos_i...i}~ có bậc không lớn hơn ~K~ thì ~left_i = left_{pos_i - 1} + 1~. Tương tự ta có ~right_i~ là độ dài dãy ngoặc đúng bậc không lớn hơn ~K~ dài nhất bắt đầu tại ~i~. Sau đó ta xét mọi dãy con ~S_{pos_i...i}~ có bậc bằng ~K~, đáp án sẽ là ~i - pos_i + 1 + left_{pos_i - 1} + right_{i + 1}~.

Vấn đề lớn nhất của bài toán bây giờ là tính bậc của một dãy ngoặc con. Ta sẽ biểu diễn ~S~ dưới dạng tổng tiền tố, nếu đặt ~'('~ là ~1~, còn ~')'~ là ~-1~ thì ta có mảng tổng tiền tố ~bal~. Xét một dãy ngoặc ~T~ bất kì, ta có mảng tiền tố ~balT~, bậc của dãy ngoặc là ~max(balT_i)~. Với một dãy ngoặc con ~S_{pos_i...i}~, ta có bậc của nó là ~max(bal_j - bal_{i - 1}) (pos_i \leq j \leq i)~ hay ~max(bal_j) - bal_{i - 1}~. Vấn đề bây giờ trở thành tìm giá trị lớn nhất của một đoạn con của mảng ~bal~, có thể giải quyết dễ dàng bằng Sparse Table hoặc Segment Tree.

Code mẫu:

#include <bits/stdc++.h>

using namespace std;

#define             MASK(i)  (1LL << (i))
#define             FULL(i)  (MASK(i) - 1)
#define                left  ___left
#define               right  ___right
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define          file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

const int MAX = 1e5 + 5;
const int LOG = 20;

string S;
int N, K, bal[MAX], pos[MAX], rmq[MAX][LOG];

void init(void) {
    cin >> S >> K;
    N = S.size(); S = ' ' + S + ' ';
}

int getMax(int l, int r) {
    int h = __lg(r - l + 1);
    return max(rmq[l][h], rmq[r - FULL(h)][h]);
}

int dp[MAX];

long long countBracket(int k) {
    long long res = 0;
    memset(dp, 0, (N + 1) * sizeof(int));
    dp[0] = 0;
    FOR(i, 1, N) if (pos[i] && getMax(pos[i], i) - bal[pos[i] - 1] <= k)
        dp[i] = dp[pos[i] - 1] + 1, res += dp[i];
    return res;
}

int left[MAX], right[MAX];

int maxBracket(int k) {
    memset(left, 0, (N + 1) * sizeof(int));
    memset(right, 0, (N + 1) * sizeof(int));

    FOR(i, 1, N) if (pos[i] && getMax(pos[i], i) - bal[pos[i] - 1] <= k) 
        left[i] = left[pos[i] - 1] + i - pos[i] + 1;

    FORD(i, N, 1) if (pos[i] && getMax(pos[i], i) - bal[pos[i] - 1] <= k)
        right[pos[i]] = right[i + 1] + i - pos[i] + 1;

    int res = -1;
    FOR(i, 1, N) if (pos[i] && getMax(pos[i], i) - bal[pos[i] - 1] == k) 
        maximize(res, left[i] + right[i + 1]);
    return res;
}

void process(void) {
    stack <int> st;
    FOR(i, 1, N) {
        bal[i] = bal[i - 1];
        if (S[i] == '(') {
            ++bal[i];
            st.push(i);
        } else {
            if (!st.empty()) {
                pos[i] = st.top();
                st.pop();
            }
            --bal[i];
        }
        rmq[i][0] = bal[i];
    }

    FOR(k, 1, LOG - 1) FOR(i, 1, N - FULL(k))
        rmq[i][k] = max(rmq[i][k - 1], rmq[i + MASK(k - 1)][k - 1]);

    cout << countBracket(K) - countBracket(K - 1) << endl;
    cout << maxBracket(K) << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
    file("kbracket");
    init();
    process();
    return (0^0);
}