这题若普通枚举遍历，需要四重for循环，时间复杂度是𝑂(𝑛2𝑚2)O(n2m2**)，相当之高，所以使用二维前缀和可以优化掉两层for循环，达到𝑂(𝑛2)O(n2)**时间复杂度，理解并使用好二维前缀和非常关键，话不多说直接贴代码：

细节的问题就是边界的处理，不要搞混了。

两位同学的题解也是非常详细的，点赞👍

#include<bits/stdc++.h>
using namespace std;
int n, a[1111][1111], sum[1111][1111];
int x, y, s;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
		}
	}
	cin >> x >> y;
	for (int i = y; i <= n; i++) {
		for (int j = y; j <= n; j++) {
			s = sum[i][j] - sum[i - y][j] - sum[i][j - y] + sum[i - y][j - y];
			if (s >= x) {
				cout << "YES";
				return 0;
			}
		}
	}
	cout << "NO";
	return 0;
}

这题若普通枚举遍历，需要四重for循环，时间复杂度是$O(n^2m^2)$，相当之高，所以使用二维前缀和可以优化掉两层for循环，达到$O(n^2)$时间复杂度，理解并使用好二维前缀和非常关键，话不多说直接贴代码：

细节的问题就是边界的处理，不要搞混了。

两位同学的题解也是非常详细的，点赞👍

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, k, m, a[N][N], sum[N][N], s;
bool flag;

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> a[i][j];
			sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];
		}
	}

	cin >> k >> m;

	for (int i = 1; i <= n - m + 1; i++)
	{
		for (int j = 1; j <= n - m + 1; j++)
		{
			s = sum[i + m - 1][j + m - 1] - sum[i - 1][j + m - 1] - sum[i + m - 1][j - 1] + sum[i - 1][j - 1];
			if (s > k)
			{
				flag = true;
				break;
			}
		}
	}

	if (flag)
		cout << "YES";
	else
		cout << "NO";

	return 0;
}

/*下次叮叮老师买奖品时记得看下钱包

不至于摆地摊吧，开个淘宝店铺都比这强*/

我是除老师外第一个尝试做这道题的（也许？） 这道题着实把我恶心到了，这道题没改前可能还比较好理解，但是，在我和老师一段时间的交流后，老师把题目改成了这个样子（所以我是带恶人）（逃）

昨晚一直纠结二维前缀和，直到刚刚看到@hetao444715的代码，我才恍然大雾，如他所说，关键是看懂二维前缀和的解释，我写出来的代码你们别笑啊

for (int i = 1; i <= n; i++)
{
    int t = sum[m + i][m + i] - sum[i][m + i] - sum[m + i][i] + sum[i][i];
    
    if (t > k)
    {
        cout << "YES" << endl;
        return 0;
    }
}

cout << "NO" << endl;

然后我跑了一遍又一遍，调试了一遍又一遍，始终是错的。 我被老师给我说的一句话限制住了思维 “这个循环只有1层” 然后我就死命写单层循环，完全忘了这是个二维数组

废话说的有点多哈

这道题的实质是在一个n * n的矩阵中选m * m的小矩阵，如样例1，在一个5 * 5的矩阵中选3 * 3的小矩阵

1 2 3 4 5

1 1 1 1 1 1

2 1 1 1 1 1

3 1 1 1 1 1

4 1 1 1 1 1

5 1 1 1 1 1

我们一共有9种选择

1. (1, 1) (3, 3)
2. (1, 2) (3, 4)
3. (1, 3) (3, 5)
4. (2, 1) (4, 3)
5. (2, 2) (4, 4)
6. (2, 3) (4, 5)
7. (3, 1) (5, 3)
8. (3, 2) (5, 4)
9. (3, 3) (5, 5)

可以发现，在矩阵允许的范围内，x1、y1有n - m + 1种可能，即int i = m; i <= n; i++，再结合https://www.cnblogs.com/acioi/p/11705205.html，理解二维前缀和（我就不概括了，懒），就能得出最终AC代码（和hetao444715差不多，真不是我抄袭啊，重申，我不是抄袭）

#include <bits/stdc++.h>

using namespace std;

int n, k, m, a[1005][1005], sum[1005][1005], ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
            sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + a[i][j];
        }
    }

    cin >> k >> m;

    for (int i = m; i <= n; i++)
    {
        for (int j = m; j <= n; j++)
        {
            ans = sum[i][j] - sum[i - m][j] - sum[i][j - m] + sum[i - m][j - m];
        
            if (ans > k)
            {
                cout << "YES" << endl;
                return 0;
            }
        }
    }

    cout << "NO" << endl;

    return 0;
}

老师写的代码真厉害，通俗易懂！ P.S.二维前缀和公式： sum[x][y] = sum[x - 1][y] + sum[x][y - 1] - sum[x - 1][y - 1] + a[x][y];

1