1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
#define ft first
#define sc second
#define pb push_back
#define FOR(i,n) for(int i=0; i<n; i++)
#define FORE(i,a,b) for(int i=a; i<=b; i++)
#define watch(x) cout << (#x) << " == " << (x) << endl
typedef long long ll;
typedef long double ld;
using namespace std;
const ll N = 1e5;
const ll min_N = 1e4;
int naw[min_N][min_N]={0};
bool s[N];
ll mmin;
int n,k;

void solve(int cnt, int last, int it, ll ans){
  if (cnt>k) {return;}
  if (it == n){
    if (cnt == k){
      mmin = min(mmin, ans+naw[last+1][n]);
    }
    return;
  }
  solve(cnt, last, it+1, ans);
  solve(cnt+1, it, it+1, ans+naw[last+1][it]);
}


int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

string sn;
cin>>n>>k>>sn;
k--;

FORE(i, 1, sn.size()){
  s[i] = (sn[i-1]=='(' ? 0 : 1);
}

FORE(i, 1, n-1){
  if (s[i]==0 && s[i+1]==1){
    naw[i][i+1]=1;
  }
}

for (int d=4; d<=n-(n%2); d+=2){
  FORE(i, 1, n-d+1){
    if (s[i+d-1]==1){
      if (s[i]==0 && naw[i+1][i+d-2]==1){
          naw[i][i+d-1]=1;
      }
      if (naw[i][i+d-1]==0){
        for (int j=i; j<=i+d-2; j++){
          if (naw[i][j]==1 && naw[j+1][i+d-1]){
            naw[i][i+d-1]=1;
            break;
          }
        }
      }
    }
  }
}

FOR(x,n+2){
  naw[0][x]=0;
}

for(int b=n; b>=1; b--){
  FORE(e, 1, n){
    naw[b][e] = naw[b][e-1] + naw[b+1][e] - naw[b+1][e-1] + naw[b][e];
  }
}

mmin = naw[1][n];
solve(0,0,1,0);
cout<<mmin;

return 0;
}