Description

Siruseri 政府决定将石油资源丰富的 Navalur 省的土地拍卖给私人承包商以建立油井. 被拍卖的整块土地为一个矩形区域, 被划分为 \(m \times n\) 个小块.

Siruseri 地质调查局有关于 Navalur 土地石油储量的估测数据. 这些数据表示为 \(m \times n\) 个非负整数, 即对每一小块土地石油储量的估计值.

为了避免出现垄断, 政府规定每一个承包商只能承包一个由 \(k \times k\) 块相连的土地构成的正方形区域.

AoE 石油联合公司由三个承包商组成, 他们想选择三块互不相交的 \(k \times k\) 的区域使得总的收益最大.

例如, 假设石油储量的估计值如下:\[ \begin{matrix} 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 \end{matrix} \] 如果 \(k = 2\), AoE 公司可以承包的区域的石油储量总和为 \(100\), 如果 \(k = 3\), AoE 公司可以承包的区域的石油储量总和为 \(208\).

AoE 公司雇佣你来写一个程序, 帮助计算出他们可以承包的区域的石油储量之和的最大值.

Input

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

Output

输出只包含一个整数, 表示 AoE 公司可以承包的区域的石油储量之和的最大值.

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

Explanation

一个很暴力的 DP, 做法有点过分~

先预处理, 对于每一个点, 考虑从这里开始选择, 向左上、右上、左下、右下四个方向分别可以选择到的最大值是多少.

然后再考虑对于以每一个点为中点, 以下方案中最好的是:

  • 向左上、右上和下方
  • 向右上、右下和左方
  • 向左下、右下和上方
  • 向左上、左下和有方

以及两种比较奇怪的分类讨论:

  • 左边、右边和中间
  • 上边、下边和中间

然后对这一坨东西取一个 max, 然后搞定.

听说用 rep 有代码长度缩短的 buff......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define per(_var,_end,_begin) for(int _var=_end;_var>=_begin;_var--)
#define max_3(__x,__y,__z) max(__x,max(__y,__z))
#define min_3(__x,__y,__z) min(__x,min(__y,__z))
#define maximize(__x,__y) __x=max(__x,__y)
#define minimize(__x,__y) __Y=min(__x,__y)
#define arr2d [maxn][maxn]
using namespace std;
typedef long long lli;
const int maxn = 2048;

int n, m, K;
int s arr2d, a arr2d, b arr2d, c arr2d, d arr2d;

int main(int argc, char** argv)
{
    scanf("%d%d%d", &n, &m, &K);
    int res = 0;
    rep(i, 1, n) rep(j, 1, m) {
        int x; scanf("%d", &x);
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + x;
    }
    // Construct (n-k) * (m-k) blocks
    per(i, n, K) per(j, m, K)
        s[i][j] -= s[i-K][j] + s[i][j-K] - s[i-K][j-K];
    // a[][], b[][], c[][], d[][], respectively represents the maximum values
    // starting from the 4 corners, on par of each block position.
    rep(i, K, n) rep(j, K, m) // Upper-Left / UL
        a[i][j] = max_3(s[i][j], a[i-1][j], a[i][j-1]);
    rep(i, K, n) per(j, m, K) // Upper-Right / UR
        b[i][j] = max_3(s[i][j], b[i-1][j], b[i][j+1]);
    per(i, n, K) rep(j, K, m) // Lower-Left / BL
        c[i][j] = max_3(s[i][j], c[i+1][j], c[i][j-1]);
    per(i, n, K) per(j, m, K) // Lower-Right / BR
        d[i][j] = max_3(s[i][j], d[i+1][j], d[i][j+1]);
    // Should they line in separate chunks, Not colliding on 1 side perpendicular
    // to horizontal / vertical axis
    rep(i, K, n - K) rep(j, K, m - K) // UL + UR + B*
        maximize(res, a[i][j] + b[i][j+K] + c[i+K][m]);
    rep(i, K, n - K) rep(j, K + K, m) // UR + BR + *L
        maximize(res, b[i][j] + d[i+K][j] + a[n][j-K]);
    rep(i, K + K, n) rep(j, K, m - K) // BL + BR + U*
        maximize(res, c[i][j] + d[i][j+K] + a[i-K][m]);
    rep(i, K, n - K) rep(j, K, m - K) // UL + BL + *R
        maximize(res, a[i][j] + c[i+K][j] + b[n][j+K]);
    // Appointing to 3 adhesing positions
    rep(i, K, n) rep(j, K + K, m - K) // L + (mid) + R
        maximize(res, s[i][j] + a[n][j-K] + b[n][j+K]);
    rep(i, K + K, n - K) rep(j, K, m) // U + (mid) + B
        maximize(res, s[i][j] + a[i-K][m] + c[i+K][m]);
    // Result GET!
    printf("%d\n", res);
    return 0;
}