hi！我是AC使者！

题目描述

KXT 是一个很无聊的小朋友，一天到晚都在打坐......

一天，被他发现了一个比打坐更无聊的事情——打砖块。很多块砖分布在一个m*mm∗m 的矩阵中，他可以消掉以他为左上角顶点的一个 n*nn∗n 的矩阵里的所有砖块。

喜欢偷懒的他请来了你帮他计算可以消掉最多的砖块数（只能消一次）。

输入格式

第一行：用空格隔开的三个整数 nn、mm、kk。

接下来 kk 行，每行 22 个用空格隔开的整数 x_ixi​、y_iyi​，表示第 ii 块砖在 x_ixi​ 行、y_iyi​ 列的位置。

数据范围

n \le mn≤m; k \le m*mk≤m∗m

60% 的数据：n \le 70n≤70; m \le 70m≤70; k \le 4900k≤4900

100% 的数据：n \le 1000n≤1000; m \le 1000m≤1000; k \le 1000000k≤1000000;

输出格式

一个整数，为可以消掉最多的砖块数。

样例

输入数据 1

5 10 11
2 1
4 6
4 9
3 9
9 7
9 9
7 9
8 10
8 8
8 6
10 2

Copy

输出数据 1

6

Copy

样例解释

站在第 4 行、 6 列的位置，可以消除 6 个方块。

答案：

#include<bits/stdc++.h>
using namespace std;
const int t=1001;
void construction(int n,int m,int array[][t],int prefix[][t])
{for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+array[i][j];}}
}
int regionsum(int n,int m,int xf,int xs,int yf,int ys,int prefix[][t])
{return prefix[xs][ys]-prefix[xf-1][ys]-prefix[xs][yf-1]+prefix[xf-1][yf-1];
}
int n,m,k,a[t][t],x,y,ma[t][t],L;
int main(){cin>>n>>m>>k;for(int i=1;i<=k;i++){cin>>x>>y;a[x][y]=1;}construction(m,m,a,ma);for(int i=1;i<=m-n+1;i++){for(int j=1;j<=m-n+1;j++){L=max(L,regionsum(m,m,i,i+n-1,j,j+n-1,ma));}}cout<<L;return 0;
}