← 返回题目列表

Codeforces · 1304/F1

F1. 动物观察(简易版)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是对 $$$k$$$ 的约束。

Gildong 喜欢观察动物,所以他买了两台相机来拍摄森林中野生动物的视频。一台相机的颜色为红色,另一台相机的颜色为蓝色。

Gildong 将拍摄 $$$n$$$ 天的视频,从 $$$1$$$ 天到 $$$n$$$ 天。森林可分为 $$$m$$$ 区域,编号从 $$$1$$$ 到 $$$m$$$。他将按以下方式使用相机:

- 在每个奇数日($$$1$$$-st、$$$3$$$-rd、$$$5$$$-th,...),将红色摄像机带到森林并录制 $$$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 min(m,20)$$$) – Gildong 要记录的天数,分别是森林的面积和摄像机的范围。

接下来的 $$$n$$$ 行每行包含 $$$m$$$ 个整数。 $$$i+1$$$-st 行中的第 $$$j$$$-th 整数是第 $$$j$$$-th 区域中第 $$$i$$$-th 天可以看到的动物数量。每个动物的数量在 $$$0$$$ 和 $$$1000$$$ 之间(含)。

输出

打印一个整数——可以观察到的动物的最大数量。

示例

输入 #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

注意

四个例子中观察动物的最佳方式如下:

示例 1:

示例 2:

示例 3:

示例 4: