SP12030 BLACKOUT - Blackout

在加拉加斯这个城市，永远都有热闹喧嚣的一面。然而，这种情况即将改变，因为马科斯“小个子”警官计划进行一些停电行动，以便搜寻一个重要的罪犯（该罪犯被称为“El Pran Malandroso”）。这个罪犯的特点是当看不到任何光源时就会晕倒，所以这对马科斯“小个子”来说是个绝佳的抓捕机会。 马科斯会给你一张地图，地图以矩阵形式表示他的搜查区域，每个值代表一个被街道包围的街区，而第 $i$ 行第 $j$ 列的数字表示该街区居住的人数。 作为一个负责任的警官，马科斯“小个子”希望尽量减少对市民的打扰，因此他会限制被打扰的人数。当他令整个区域陷入黑暗时，市民可能会非常不满。为此，他会指定西北角和东南角的位置，在这一区域进行搜查，并导致停电。 马科斯将在夜间进行多次停电，每次停电在一个指定区域进行，然后恢复灯光，再进行下一次。这样反复操作，进行 $Q$ 次停电。因为罪犯在城市中不断游荡，所以每次停电都是独立的，搜索区域也各不相同。 在这种情况下，你能否确保在不超过打扰人数限制的情况下，使得搜索区域的面积最大化？ **输入格式：** 第一行包含四个整数 $N$、$M$、$Q$ 和 $K$，分别表示表示城市俯视图的矩阵大小 $N \times M$、马科斯“小个子”计划进行的停电次数 $Q$，以及最大允许打扰的人数 $K$。 接下来是 $N$ 行，每行有 $M$ 个整数，代表每个街区的居民数量。 随后有 $Q$ 行，每行有四个整数，代表西北角 $(i, j)$ 和东南角 $(i, j)$ 的坐标。 **输出格式：** 输出一行，包含一个整数，表示马科斯能够搜索的最大区域面积。 **样例 1：** **输入** 3 3 2 20 1 2 3 4 5 6 7 8 9 1 1 3 3 1 1 2 2 **输出** 4 注意，每次停电是独立的。例如，影响从 (1,1) 到 (3,3) 的区域将导致 45 人不满，覆盖 9 单位的面积；而从 (1,1) 到 (2,2) 的停电只会影响 12 人，覆盖 4 单位的面积。如果限制为 57，人们可以接受这两次停电，总共覆盖 13 单位的面积。 **样例 2：** **输入** 4 3 3 76 1 4 9 5 5 2 2 1 9 9 1 9 2 1 4 3 1 1 4 3 2 1 3 2 **输出** 16 **数据范围与提示：** - $1 \leq N, M \leq 2000$ - $1 \leq Q \leq 1000$ - $1 \leq K \leq 1000$ - $0 \leq N_i, M_j \leq 1000$ 保证至少有一个停电方案不会打扰超过 $K$ 的人。 **本翻译由 AI 自动生成**

无

无