rt，没加快读 TLE on #12 ，现在加了快读 & register ，被 #45 卡了（ n 都是 4000，中间还过了很多 3000 多的点）

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define R register
#define INF (0x3f3f3f3f)
using namespace std;

char buf[1000000], *p1 = buf, *p2 = buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
inline int read() {
	R int x = 0; char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x;
}

const int MAXN = 4005;

int n, K;
int sum[MAXN][MAXN];
int dp[MAXN][MAXN];
inline int Calc(R int x, R int y) {
	return sum[y][y] - sum[x - 1][y] - sum[y][x - 1] + sum[x - 1][x - 1];
}

inline void Solve(R int t, R int l, R int r, R int optl, R int optr) {
	if (l > r) return;
	R int mid = (l + r) >> 1, opt = 0;
	for (R int i = optl; i <= mid; ++ i)
		if (dp[mid][t] > dp[i - 1][t - 1] + Calc(i, mid))
			opt = i, dp[mid][t] = dp[i - 1][t - 1] + Calc(i, mid);
	Solve(t, l, mid - 1, optl, opt);
	Solve(t, mid + 1, r, opt, optr);
}

int main()
{
	n = read(), K = read();
	for (R int i = 1; i <= n; ++ i)
		for (R int j = 1; j <= n; ++ j) {
			sum[i][j] = read();
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0] = 0;
	for (R int i = 1; i <= K; ++ i) 
		Solve(i, 1, n, 1, n);
	return printf ("%d\n", dp[n][K] / 2), 0;
}