Animal Observation (hard version)

题意翻译

简单版和困难版唯一的区别是 $k$ 的范围。 Gildong 计划拍摄森林中的野生动物们。森林被划分为 $m$ 个地区，依次编号为 $1$ 到 $m$，他的拍摄计划持续 $n$ 天。 每一天，他会选择森林中连续的 $k$ 个地区，并且录一段长为 $2$ 天的录像。（如果是最后一天，那就录一段长度为 $1$ 天的录像）这样所有在这两天之内在这 $k$ 个地区中出现过的动物都会被拍摄到。 他知道未来 $n$ 天内每一天每一个地区会出现多少野生动物。他想拍摄下尽可能多的野生动物。注意如果一个动物被拍摄了两次，那么只会被计算一次。 你的任务是求出拍摄到的动物数量的最大值。 $n\le 50,m\le 20000,k\le m$

题目描述

The only difference between easy and hard versions is the constraint on $ k $ . Gildong loves observing animals, so he bought two cameras to take videos of wild animals in a forest. The color of one camera is red, and the other one's color is blue. Gildong is going to take videos for $ n $ days, starting from day $ 1 $ to day $ n $ . The forest can be divided into $ m $ areas, numbered from $ 1 $ to $ m $ . He'll use the cameras in the following way: - On every odd day ( $ 1 $ -st, $ 3 $ -rd, $ 5 $ -th, ...), bring the red camera to the forest and record a video for $ 2 $ days. - On every even day ( $ 2 $ -nd, $ 4 $ -th, $ 6 $ -th, ...), bring the blue camera to the forest and record a video for $ 2 $ days. - If he starts recording on the $ n $ -th day with one of the cameras, the camera records for only one day. Each camera can observe $ k $ consecutive areas of the forest. For example, if $ m=5 $ and $ k=3 $ , he can put a camera to observe one of these three ranges of areas for two days: $ [1,3] $ , $ [2,4] $ , and $ [3,5] $ . Gildong got information about how many animals will be seen in each area on each day. Since he would like to observe as many animals as possible, he wants you to find the best way to place the two cameras for $ n $ days. Note that if the two cameras are observing the same area on the same day, the animals observed in that area are counted only once.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ , and $ k $ ( $ 1 \le n \le 50 $ , $ 1 \le m \le 2 \cdot 10^4 $ , $ 1 \le k \le m $ ) – the number of days Gildong is going to record, the number of areas of the forest, and the range of the cameras, respectively. Next $ n $ lines contain $ m $ integers each. The $ j $ -th integer in the $ i+1 $ -st line is the number of animals that can be seen on the $ i $ -th day in the $ j $ -th area. Each number of animals is between $ 0 $ and $ 1000 $ , inclusive.

输出格式

Print one integer – the maximum number of animals that can be observed.

输入输出样例

输入样例 #1

4 5 2
0 2 1 1 0
0 0 3 1 2
1 0 4 3 1
3 3 0 0 4

输出样例 #1

25

输入样例 #2

3 3 1
1 2 3
4 5 6
7 8 9

输出样例 #2

31

输入样例 #3

3 3 2
1 2 3
4 5 6
7 8 9

输出样例 #3

44

输入样例 #4

3 3 3
1 2 3
4 5 6
7 8 9

输出样例 #4

45

说明

The optimal way to observe animals in the four examples are as follows: Example 1: Example 2: Example 3: Example 4: 

题意翻译

简单版和困难版唯一的区别是 $k$ 的范围。 Gildong 计划拍摄森林中的野生动物们。森林被划分为 $m$ 个地区，依次编号为 $1$ 到 $m$，他的拍摄计划持续 $n$ 天。 每一天，他会选择森林中连续的 $k$ 个地区，并且录一段长为 $2$ 天的录像。（如果是最后一天，那就录一段长度为 $1$ 天的录像）这样所有在这两天之内在这 $k$ 个地区中出现过的动物都会被拍摄到。 他知道未来 $n$ 天内每一天每一个地区会出现多少野生动物。他想拍摄下尽可能多的野生动物。注意如果一个动物被拍摄了两次，那么只会被计算一次。 你的任务是求出拍摄到的动物数量的最大值。 $n\le 50,m\le 20000,k\le m$