题解

我们需要选择 $r$ 条水平切线与 $s$ 条竖直切线，使得每个小矩形的权值和不超过某个上限 $W$，并让 $W$ 尽量小。由于 $n,m\le 18$，横向切的位置数量不多，可以先枚举竖向切点，再对每种竖向切法做二分/检查：

1. 枚举竖划分：用一个位掩码表示在第 $j$ 条子午线之后是否切一刀。这样可以把列分成若干连续段（不超过 $s+1$ 段），限制超过就跳过。
2. 前缀和预处理：对每行求前缀和 sum[i][j]，方便在 $O(1)$ 时间求出某行某个列段的权值。
3. 给定竖划分后二分答案：下界设为单个行段所需的最大值，上界为总和 all。检查函数 check(mid) 按行从上到下累积每个竖直段的和，如果某段超过 mid 就认为必须在上一行切一条水平线，并清空累积值。统计所需的水平切线条数，若不超过 $r$ 即可。

对子集枚举与二分取最小值。由于竖向有 $m-1$ 个潜在切点，枚举的次数为 $O(2^{m-1})$，每次检查在 $O(n \cdot \text{段数})$ 时间内完成，总体复杂度在数据范围内轻松通过。

# include <bits/stdc++.h>
using namespace std;
const int N = 20 + 5, M = 20 + 5;
int n, m, rmax, smax;
int a [N] [M], sum [N] [M];
int l [M], r [M];
int all = 0;
int sz [M];
int check (int w, int tot) {
	int cnt = 0;
	for (int i = 1; i <= tot; ++ i) {
		sz [i] = 0;
	}
	for (int i = 1; i <= n && cnt <= rmax; ++ i) {
		for (int j = 1; j <= tot; ++ j) {
			sz [j] += sum [i] [r [j]] - sum [i] [l [j] - 1];
		}
		for (int j = 1; j <= tot; ++ j) {
			if (sz [j] > w) {
				for (int k = 1; k <= tot; ++ k) {
					sz [k] = sum [i] [r [k]] - sum [i] [l [k] - 1];
				}
				++ cnt;
				break;
			}
		}
	}
	return cnt <= rmax;
}
int Search (int tot) {
	int L = 0, R = all, ans = all;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= tot; ++ j) {
			L = max (L, sum [i] [r [j]] - sum [i] [l [j] - 1]);
		}
	}
	while (L <= R) {
		int mid = (L + R) >> 1;
		if (check (mid, tot)) {
			ans = mid;
			R = mid - 1;
		}
		else { 
			L = mid + 1;
		}
	}
	return ans;
}
int main () {
	scanf ("%d %d %d %d", & n, & m, & rmax, & smax);
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			scanf ("%d", & a [i] [j]);
			all += a [i] [j];
		}
	}
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= m; ++ j) {
			sum [i] [j] = sum [i] [j - 1] + a [i] [j];
		}
	}
	int ans = all;
	for (int i = 0; i < (1 << (m - 1)); ++ i) {
		int tot = 1;
		l [1] = 1;
		for (int j = 1; j <= m - 1; ++ j) {
			if ((i >> (j - 1)) & 1) {
				r [tot] = j;
				++ tot;
				l [tot] = j + 1;
			}
		}
		r [tot] = m;
		if (tot > smax + 1) {
			continue;
		}
		ans = min (ans, Search (tot));
	}
	printf ("%d", ans);
	return 0;
}