Skip to content

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

208

Limits

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

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

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

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

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

Oops! 本题目还没有解答!

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

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

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