CF1304F2 Animal Observation (hard version)
题目描述
简单版与困难版的唯一区别在于 $k$ 的限制。
Gildong 喜欢观察动物，因此他买了两台摄像机来拍摄森林中的野生动物。一台摄像机是红色的，另一台是蓝色的。
Gildong 计划在 $n$ 天内（从第 $1$ 天到第 $n$ 天）进行拍摄。森林被划分为 $m$ 个区域，编号从 $1$ 到 $m$。他将按如下方式使用摄像机：
- 在每个奇数天（第 $1$、$3$、$5$ 天……），他会带上红色摄像机到森林中，并连续拍摄 $2$ 天。
- 在每个偶数天（第 $2$、$4$、$6$ 天……），他会带上蓝色摄像机到森林中，并连续拍摄 $2$ 天。
- 如果他在第 $n$ 天开始用某台摄像机拍摄，则该摄像机只拍摄一天。
每台摄像机可以观察森林中连续的 $k$ 个区域。例如，如果 $m=5$ 且 $k=3$，他可以选择让摄像机在两天内观察以下三个区域区间之一：$[1,3]$、$[2,4]$、$[3,5]$。
Gildong 已经得知每一天每个区域能看到多少只动物。由于他希望观察到尽可能多的动物，请你帮他规划 $n$ 天内两台摄像机的最佳放置方式。注意，如果两台摄像机在同一天观察了同一个区域，则该区域的动物只计数一次。
输入格式
第一行包含三个整数 $n$、$m$、$k$（$1 \le n \le 50$，$1 \le m \le 2 \cdot 10^4$，$1 \le k \le m$）——Gildong 拍摄的天数、森林的区域数以及摄像机的可观察范围。
接下来的 $n$ 行，每行包含 $m$ 个整数。第 $i+1$ 行的第 $j$ 个整数表示第 $i$ 天在第 $j$ 个区域能看到的动物数量。每个动物数量在 $0$ 到 $1000$ 之间。
输出格式
输出一个整数，表示最多能观察到的动物数量。
说明/提示
四个样例的最优观察方式如下：
样例 1：
样例 2：
样例 3：
样例 4：
由 ChatGPT 4.1 翻译