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
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <algorithm>
#include <vector>
#include <iostream>
#include <climits>

using ll = long long;

std::vector<std::vector<ll>> dp;
std::vector<std::vector<ll>> cost;

// Divide and conquer optimization (thank u ld)
void dodp(int j, int p, int q, int l, int r) {
	if (p > q) return;
	
	int mid = (p+q)/2;
	
	ll mincst = LLONG_MAX;
	int optk;
	for (int k = l; k <= std::min(r, mid); ++k) {
		ll cst = cost[k][mid] + dp[k-1][j-1];
		if (cst < mincst) {
			mincst = cst;
			optk = k;
		}
	}
	
	dp[mid][j] = mincst;
	
	dodp(j, p, mid-1, l, optk);
	dodp(j, mid+1, q, optk, r);
}

int main() {
	std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);
	
	int n, K;
	std::cin >> n >> K;
	
	std::string input;
	std::cin >> input;
	
	// dp[i][j] -- minimal cost of dividing input[0..i] into j segments
	// cost[i][j] -- cost of the segment input[i..j]
	dp.assign(n, std::vector<ll>(K+1));
	cost.assign(n, std::vector<ll>(n));
	
	// we calculate cost[][] in O(n²)
	for (int i = 0; i < n; ++i) {
		ll cst = 0;
		std::vector<int> stack;
		int toplvl = 0;
		int j = i;
		while (j < n) {
			if (input[j] == '(') {
				stack.push_back(0);
			} else if (!stack.empty()) {
				stack.pop_back();
				if (stack.empty()) {
					cst += ++toplvl;
				} else {
					cst += ++stack.back();
				}
			} else {
				toplvl = 0;
			}
			cost[i][j] = cst;
			++j;
		}
	}
	
	// now we calculate dp[][] in O(n³)
	// TODO: can this be optimized with a known trick?
	
	// the divide and conquer trick aint good -- counterexample:
	// 300 300
	// )()(())))()()((())))((())))())()((()())()())(())))(())))())(()()())))()(()))))())((())(()))(())(((()(()))((()()))((()((()()(((()))(()((()(())()((()())())))()((())())))((((())))(())()()))(()(()))(()((()((()()()))))())))(()(())()()(((((())(()()())))(())))(((()()(()))))(()(()))(()(())((((((()()((()()((
	// j=4: optk[214]=151; optk[215]=61; (with 0-based indexing)
	// SIKE! calculating cost[][] was buggy. Divide and conquer actually works!!!
	
	for (int i = 0; i < n; ++i) {
		dp[i][1] = cost[0][i];
	}
	
	for (int j = 2; j <= K; ++j) {
		dp[j-1][j] = 0;
		dodp(j, j, n-1, j-1, n-1);
	}
	
	std::cout << dp[n-1][K] << '\n';
	
	/*for (int j = 1; j <= K; ++j) {
		std::cout << "j=" << j << ":";
		for (int i = 0; i < n; ++i) {
			std::cout << ' ' << dp[i][j];
		}
		std::cout << '\n';
	}*/
	
	/*
	for (int i = 0; i < n; ++i) {
		dp[i][1] = cost[0][i];
	}
	for (int j = 2; j <= K; ++j) {
		dp[j-1][j] = 0;
		std::vector<std::vector<int>> optks(n);
		for (int i = j; i < n; ++i) {
			ll mincst = LLONG_MAX;
			std::vector<int> optk;
			for (int k = j-1; k <= i; ++k) {
				ll cst = cost[k][i] + dp[k-1][j-1];
				if (cst < mincst) {
					optk.clear();
				}
				mincst = std::min(mincst, cst);
				if (cst == mincst) {
					optk.push_back(k);
				}
			}
			dp[i][j] = mincst;
			optks[i] = std::move(optk);
		}
		for (int i = j+1; i < n; ++i) {
			int minprevk = *std::min_element(optks[i-1].begin(), optks[i-1].end());
			int maxherek = *std::max_element(optks[i].begin(), optks[i].end());
			if (minprevk > maxherek) std::cout << "dupa: j=" << j << "; min(optks[" << i-1 << "])=" << minprevk << "; max(opks[" << i << "])=" << maxherek << '\n';
		}
	}
	
	std::cout << dp[n-1][K] << '\n';
	*/
	
	return 0;
}