本来打算先写暴力 DP 的，然后过了。

这是 check 的代码：

bool check(int k) {
	for (int i = 0; i <= sz; ++i) for (int j = 0; j <= k; ++j) f[i][j] = 0;
	f[0][0] = 1;
	int tot = 0;
	for (int i = 0; i < sz; ++i) for (int j = 0; j <= k; ++j) {
		if (!f[i][j]) continue;
		int c = cnt[i + 1];
		for (int p = max(c + j - k, 0); p <= min(j, c); ++p) if (j + c - p * 2 >= 0 && j + c - p * 2 <= k)
			f[i + 1][j + c - p * 2] = 1, prv[i + 1][j + c - p * 2] = p, ++tot;
	}
	return f[sz][0];
}

很疑惑，然后试图卡掉自己，感觉卡不掉。

瞪了一眼发现 $i,p$ 的总数就是 $\mathcal{O}(n)$ 的啊？那复杂度不就是 $\mathcal{O}(nk)$ 的么？这就是对的吧（

求解答。