11585: 【原1585】Oil

题目描述

author: Crystal 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1585

Description

Crystal家的公司最近承包了一个大油田。整块油田为一个矩形区域，被划分为 n X m 个小块。 Crystal亲自调查了每个小块的石油储备量。这些数据表示为n X m个非负整数。但是Crystal现在心情不好，只想开采三个由k X k块相连的土地构成的正方形区域。这些正方形区域必须互不重叠。现在，Crystal想让你帮忙计算出她最多能开采出多少石油。

Input Format

第一行三个整数n, m, k。

接下来n行，每行m个整数，表示每个小块的储油量。

Output Format

一个整数，表示Crystal最多能开采出多少石油。

Sample Input

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

Sample Output

Limits

对于100%的数据保证有解。

对于40%的数据，保证n, m, k <= 12。

对于70%的数据，保证n, m, k <= 500。

对于100%的数据，保证n, m, k <= 1500。

对于100%的数据，保证所有输入数据均为非负整数，且在int范围内。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！