洛谷P2004 领地选择

url: https://www.luogu.com.cn/problem/P2004

tag：
前缀和

思路：
先求前缀和，然后遍历右下端点，求出每个对应的子矩阵的总和，判断是否大于res，如果大的话就更新res和坐标x，y。最后输出x和y即可。

ps：这道题很简单，本来不应该传博客的，但是觉得自己写的好优美，忍不住传一下，以后偶尔可以翻出来看看。真的好优美感觉。

代码：

#include <iostream>
using namespace std;
const int N = 1010;
long long p[N][N];
int n, m , c;
int main()
{
    cin >> n >> m >> c;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
        {
            cin >> p[i][j];
            p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        }
    long long res = 0, x, y;
    for (int i = c; i <= n; i ++)
        for (int j = c; j <= m; j ++)
        {
            long long tmp = p[i][j] - p[i - c][j] - p[i][j - c] + p[i - c][j - c];
            if (tmp > res)
            {
                res = tmp;
                x = i - c + 1;
                y = j - c + 1;
            }
        }
    cout << x << ' ' << y;
    return 0;
}