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
#include <cstdio>
#include <vector>

const int max_n = 200000;
const long long inf = 1000000000000000000LL;

int n, k;
char in[max_n];

int oc[2 * max_n];
int connected[max_n];
long long prefCount[max_n];
long long prefEndCount[max_n];

long long dp[2][max_n];


int main() {
  scanf("%d %d", &n, &k);
  scanf("%s", in + 1);

  for (int i = 0; i <= 2 * n - 1; ++i) {
    oc[i] = -1;
    connected[i] = -1;
    prefCount[i] = 0;
    prefEndCount[i] = 0;
  }

  int balans = n;
  for (int i = 1; i <= n; ++i) {
    if (in[i] == '(') {
      oc[balans] = i;
      ++balans;
    } else {
      --balans;
      if (oc[balans] != -1) {
        connected[i] = oc[balans];
      }
    }
  }
  int step = 0;
  for (int i = 0; i <= n; ++i) dp[0][i] = inf;
  dp[0][0] = 0;
  for (int i = 1; i <= k; ++i) {
    for (int j = 0; j <= n; ++j) dp[1 - step][j] = inf;
    for (int j = 0; j < n; ++j) {
      if (dp[step][j] < inf) {
        prefCount[j] = prefEndCount[j] = 0;
        for (int l = j + 1; l <= n; ++l) {
          if (in[l] == '(') {
            prefCount[l] = prefCount[l - 1];
            prefEndCount[l] = 0;
          } else {
            if (connected[l] != -1 && connected[l] >= j + 1) {
              prefCount[l] = prefCount[l - 1];
              prefEndCount[l] = 0;
              int from = connected[l];
              int to = i;
              prefCount[l] += prefEndCount[from - 1] + 1;
              prefEndCount[l] += prefEndCount[from - 1] + 1;
            } else {
              prefCount[l] = prefCount[l - 1];
              prefEndCount[l] = 0;
            }
          }
          dp[1 - step][l] = std::min(dp[1 - step][l], dp[step][j] + prefCount[l]);
        }
      }
    }
    step = 1 - step;
  }
  printf("%lld\n", dp[step][n]);
//  for (int i = 1; i <= n; ++i) {
//    printf("%c %d %d\n", in[i], prefCount[i], prefEndCount[i]);
//  }
  return 0;
}