/ Vijos / 题库 /

N大牛吃草

N大牛吃草

背景

N大牛在家种种田啊,宰宰猪啊好闲的,这种日子实在不好过,所以有天他做梦做石油承包商。

描述

梦中某政府决定将面包资源丰富的某省的土地拍卖给私人承包商N大牛以建立面包井。被拍卖的整块土地是一个矩形区域,被划分为M*N小块。

政府地质调查局有关于该省土地面包储量的估测数据。这些数据表示为M*N个非负整数,即对每一个小块土地面包储量的估计值。

政府规定一次只能承包一个由k*k块相连的土地构成的正方形区域。N大牛决定分三次承包土地,又gie又喜欢吃面包的N大牛想选择三块互不相交的k*k的区域使得总收益最大。

格式

输入格式

输入第一行包含三个整数M,N,K,其中M和N是矩形区域的行数和列数,K是每一个承包商承包的正方形的大小(边长的块数)。接下来M行,每行N非负整数表示这一行每一小块土地的石油储量的估计值。

N,M<=1500,K<=M且K<=N,每一小块土地的是有储量的估计值是非负整数且<=500。

输出格式

输出只包含一个整数,表示N大牛可以承包的区域的石油储量之和的最大值。

样例1

样例输入1

9 9 3
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8 
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9

样例输出1

208

限制

各个测试点1.5s

来源

某鸟

信息

ID
1479
难度
8
分类
动态规划 点击显示
标签
(无)
递交数
305
已通过
32
通过率
10%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库