#include <iostream>

using namespace std;

#define N 5002
int f[N][N];

int main() {

    int n, r;
    int max_x, max_y;
    int x = 0, y = 0, w = 0;
    cin >> n >> r;
    r = min(r, 5001); // 爆炸范围超过5001时覆盖了所有目标范围，因此没必要考虑超出范围。
    max_x = max_y = r;// 最小的爆炸计算范围是在一个最小爆炸范围之内计算
    for (int i = 0; i < n; ++i) {
        cin >> x >> y >> w;
        f[++x][++y] += w; // 将目标范围统一偏移1，便于边界计算。
        max_x = max(x, max_x); // 如果有目标落在一个最小爆炸范围之外，则扩大计算范围。
        max_y = max(y, max_y);
    }
    // 下面两个循环的计算公式都需要自己用手画一下，才能获得利用二维前缀和计算总价值的结果
    for (int i = 1; i <= max_x; ++i) { // 循环从偏移的1开始
        for (int j = 1; j <= max_y; ++j) {
            f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];
        }
    }

    int ans = 0;
    for (int i = r; i <= max_x; ++i) {
        for (int j = r; j <= max_y; ++j) {
            ans = max(ans, f[i][j] - f[i - r][j] - f[i][j - r] + f[i - r][j - r]);
        }
    }

    cout << ans << endl;

    return 0;
} 

谢谢大佬提示：爆炸范围超过5001时覆盖了所有目标范围，因此没必要考虑超出范围。

就是把算法进阶指南直接超上来的也能排第一名题解？？？

这个格子个点考虑起来确实是等价的，但是想着好烦啊T T

同感

为什么一直报MLE

#自己写的代码最后输入是从左上角的点开始的，所以不用考虑右下角的点是否在边长范围里的情况。

#include<bits/stdc++.h>
using namespace std;
const int N=5010;

int s[N][N];
void yuchuli()
{
    for(int i=1;i<=5001;i++)
    for(int j=1;j<=5001;j++)
    s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];//预处理前缀和的另外一种方式
}

int main()
{
    int n,r;
    cin>>n>>r;
    int res=0;//记录总价值
    while(n--)
    {
        int x,y,w;
        cin>>x>>y>>w;
        s[x+1][y+1]+=w;

    }

    if(r>=5001)
  for(int i=1;i<=5001;i++)
  for(int j=1;j<=5001;j++)
  res+=s[i][j];

    else
{
    yuchuli();
    for(int i=1;i<=5001-r;i++)
    for(int j=1;j<=5001-r;j++)
    {
      int sum=s[i+r-1][j+r-1]-s[i+r-1][j-1]-s[i-1][j+r-1]+s[i-1][j-1];
        res=max(res,sum);

    }

}
    cout<<res;
    return 0;
}

哥们你这个预处理之后的for循环里的5001应该改成5002，边界情况漏了

有没有大佬看看哪里错了= =
#include[HTML_REMOVED]
using namespace std;
int n,r;
int const N = 5010;
int s[N][N];
int main(){
cin >> n >> r;
r = min(5001 , r);
int m1 = 0 , m2 = 0;
while(n–){
int x, y, w;
cin >> x >> y >> w;
x , y;
s[x][y] += w;
}
for(int i = 1; i <= 5001; i){
for(int j = 1; j <= 5001; j){
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
}
int res = 0;
for(int i = r; i <= m1; i){
for(int j = r; j <= m2; j){
int tmp = s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r];
res = max(res , tmp);
}
}
cout << res;

}

这道题用差分是不是也是一样的鸭

为什么把5001换成输入的x、y的最大值就有一组数据ac不了呢
#include [HTML_REMOVED]
#include [HTML_REMOVED]

using namespace std;

const int N = 5010;
int w[N][N];
int n,r,i,j,k,we;
int max_x = 1e-6, max_s ,max_y =1e-6;

int main(){
cin >> n >> r;
if(r>5000) r=5001;
for(i=0;i<n;i++){
scanf(“%d %d “,&j,&k);
max_x = max(max_x,j);
max_y = max(max_y,k);

    cin >> we;
    w[++j][++k]+=we;
}
for(i=1;i<=max_x;i++){
    for(j=1;j<=max_y;j++){
        w[i][j] = w[i-1][j] + w[i][j-1] - w[i-1][j-1] + w[i][j];}
    }
for(i=r;i<=max_x;i++){
    for(j=r;j<=max_y;j++){
        max_s = max(max_s,w[i][j]-w[i-r][j]-w[i][j-r]+w[i-r][j-r]);
    }
}

cout << max_s << endl;
return 0;

}

题目有组数据是超5000的就是所有的全部轰炸了，所以必须用5001

我也是啊，有一个过不了

5001反而过的更少

我都可以过，你看看是不是你的理解问题

已经过掉了，用的是最大值

那个0.5的转换不懂啊~┭┮﹏┭┮ “而右下角处于格子交点上....”这里的x.5是啥呢？谢谢回复~

注：最终答案里的那个表达式代表的是，以(i,j)为右下角顶点，边长为r的一个正方形区域

请问我下面这个代码有什么问题吗？
#include [HTML_REMOVED]
using namespace std;
//#define int long long

const int M = 10001;
int g[M][M];

void solve() {
int N, R;
cin >> N >> R;
R = min(R, 5001);
int n = R, m = R;
for (int i = 0, x, y, w; i < N; i ) {
cin >> x >> y >> w;
x;
y;
n = max(n, x), m = max(m, y);
g[x][y] += w;
}
// for (int i = 1 ; i <= n; i ) {
// for (int j = 1; j <= m; j++)
// cout << setw(4) << g[i][j];
// cout << endl;

for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= m; j ++) {
        g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
    }
}
int res = 0;
for (int i = R; i <= n; i++) {
    for (int j = R; j <= m; j ++) {
        res = max(res, g[i][j] - g[i - R][j] - g[i][j - R] + g[i - R][j - R]);
    }
}
cout << res << endl;

}

signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T–)
solve();
return 0;
}

有没有大佬帮我看看我的码为什么Ac不了，目标比较少的时候还可以正确的通过，目标数量多起来就无法通过了

#include<iostream>
using namespace std;
const int MAXSIZE = 5010;

int main(){ 
    int N = 0;
    int R = 0;
    int x = 0;
    int y = 0;
    int w = 0;
    int wmax = 0;
    int xmax = 0;
    int ymin = 0;
    int xmin = 0;
    int ymax = 0;
    int arr[MAXSIZE][MAXSIZE];

    cin >> N >> R;

    R-=1;   //修正炸弹半径（若输入R为1，则修正为0，代表向外扩展的范围为0）

    for(int i = 0;i<N;i++){ //向arr中添加目标及价值
        cin >> x >> y >> w;
        xmax = max(x,xmax);
        ymax = max(y,ymax);
        xmin = min(x,xmin);
        ymin = min(y,ymin);
        arr[x][y]+=w;
    }

    for(int i = 0;i < MAXSIZE;i ++){ //求二维前缀和
        for(int j = 0;j < MAXSIZE;j ++){
            if(i == 0&&j>0)
                arr[i][j] = arr[i][j] + arr[i][j-1];
            if(j == 0&&i>0)
                arr[i][j] = arr[i][j] + arr[i-1][j];
            if(i>0&&j>0)
                arr[i][j] = arr[i][j] + arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1];
        }
    }

    for(int i = xmin;i+R<=xmax;i++){    //遍历取数
        for(int j = ymin;j+R<=ymax;j++){
            wmax = max(wmax,arr[i+R][j+R]+arr[i-1][j-1]-arr[i-1][j+R]-arr[i+R][j-1]);   //求取该位置炸弹破坏的价值
        }
    }

    cout << wmax;
    return 0;
}

%%%%%%%

为什么会SF啊

没有问题啊

绷不住咯 没考虑会重复赋值

#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)

这是在干什么

前面那个是读入输入的优化，是给cin/cout 提速的，
tie是用来接触cin和cout的绑定，也是加快执行效率的。

这样为啥不对呀？最后求结果时从左上角看。应该是等价的吧，搞不懂

#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int n,r,a[N][N],s[N][N],res;

int main(){
    cin>>n>>r;
    r=min(r,5001);//因为输入的横纵坐标最大差5000；

    for(int i=0;i<n;i++){
        int x,y,w;
        cin>>x>>y>>w;
        s[++x][++y]+=w;
    }
    //输入的有价值的横纵坐标最大为5000；在输入时已经把从（0,0）开始变成了（1,1）
    for (int i = 1; i <= 5001; i ++ )
        for (int j = 1; j <= 5001; j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];

    for(int i=1;i<=5001-r;i++){
        for(int j=1;j<=5001-r;j++){
            res=max(res,s[i+r][j+r]-s[i][j+r]-s[i+r][j]+s[i][j]);
        }
    }

    cout<<res<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,R;
const int N=5010;
int s[N][N];
int x,y,w;
int total;
int res=-1;
int m,q;
int main()
{
    cin >> n >> R;
    q=m=R;

    for(int i = 0;i < n;++i)
    {
        cin >> x >> y >> w;
        x++;
        y++;
        m=max(m,x);
        q=max(q,y);
        s[x][y] += w;
        total+=w;
    }

    if(R>=5000)
    {
        cout << total << endl;
        return 0;
    }
    for(int i = 1;i <= m;++i)
        for(int j=1;j <= q;++j)
        {
            s[i][j]+=s[i][j-1]+s[i-1][j]-s[i-1][j-1];
        }

    R--;
    for(int i = 1;i+R <= m;++i)
    {
        for(int j = 1;j+R <= q;++j)
        {
            int resTemp=s[i+R][j+R]-s[i+R][j-1]-s[i-1][j+R]+s[i-1][j-1];
            res=max(res,resTemp);
        }
    }
    cout << res << endl;
    return 0;
}

我是这么写的

r-1 体现在哪

r=1时只有一个格子，但是二维数组的x，y都是从1开始的，子矩阵前缀和是右下角减左上角，也就是右下角的坐标是x=x+r,y=y+r,当r=1时右下角坐标是（2，2）这样是2x2的格子，所以r要减1.

这个为啥会报 Segmentation Fault 啊

#include<iostream>
#include<algorithm>

using namespace std;

const int N=5e3+10;
int s[N][N];
int n,r;

int main()
{
    cin>>n>>r;
    r=min(5001,r);
    while(n--)
    {
        int x,y,w;
        cin>>x>>y>>w;
        s[++x][++y]+=w;
    }

    for(int i=1;i<=5001;i++)
    {
        for(int j=1;j<=5001;j++)
        s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    }

    int res=0;

    for(int i=r;i<=5001;i++)
    for(int j=r;j<=5001;j++)
    res=max(res,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);

    cout<<res<<endl;

   return 0;    
}

我也是同样报错 但我直接头铁提交 还是AC了

hhh我提交就报这个错误

不知道是什么错误 我复制你的代码直接提交还是AC了

R的范围好像是1到1e9吧……最后循环更新res那里，i和j都是不超5e3的，i-r 和 j-r 是有可能超出数组定义范围的吧？应该是这里访问了不合法的地址然后SF了

但R不是一开始就通过min(5001, R)使得R最大也就5001吗？而且我用的max_x, max_y代替循环时的判断条件上限5001，本想优化来着，结果调试一下午了都没过，蚌埠住了。

为什么右移一位就可以不考虑边界？这个边界指的是什么

前缀和数组从1开始计算

这个边界就是S矩阵的最上面一排和最左边一排，x，y就是向右下方移动吧。如果考虑边界的话会非常讨厌，处理前缀和数组的话，要先求两个一维前缀和，再求一个二维前缀和，然后处理这样一个考虑边界的二维前缀和还要分情况讨论，因为【i-1】【j-1】可能会等于-1，非常麻烦，所以说还是不考虑博边界的好。