U229852 [sxyz NOIP 模拟赛] 4 区间覆盖（range）

[sxyz NOIP 模拟赛]4 区间覆盖（range）T4 ------------ 3s 512MB

给定一个 n ∗ m 的网格和一个整数 k，网格上每个位置有一个数字 $a_{i,j}$ (1 ≤ i ≤n, 1 ≤ j ≤ m)。 对于所有 i, 1 ≤ i ≤ n，你可以指定一个区间 [l, r], 1 ≤ l ≤ r ≤ m, r − l + 1 ≤ k，然后将所有 $a_{x,y}$, n ≤ x ≤ min(n, i + 1), l ≤ y ≤ r 覆盖一次。 你需要求出，对于所有指定区间的方案，被覆盖的所有数的和的最大值是多少。在本题中，一个数字如果被覆盖多次，这个数字也只会被计算一次。

第一行三个整数 n, m, k 接下来 n 行，每行 m 个整数，表示 $a_{i,j}$

一行一个整数，表示你的答案。

4.4 数据范围与提示 对于 40% 的数据，m ≤ 100 对于 80% 的数据，k ≤ 20 对于所有数据，1 ≤ n ≤ 50, 1 ≤ m ≤ 20000, 1 ≤ k ≤ m, 0 ≤ $a_{i,j}$ ≤ 1000